The main story was of a war between the Ura (Zia & Zulf are Ura) & the Caelondians (like Kid & the narrator) which resulted in the Calamity (mass destruction of both civilizations). In our terms think of Caelondians as an advanced western society and the Ura as a more primitive eastern who lived "underground". Ura refugees were allowed in Caelondia as long as they never went back to their home, the Tazal Terminals, but there was still a lot of racism and they were watched closely by the Marshals/Mancers of the city. They were regarded as potential traitors who would sell out city secrets to the Tazal Terminals if they were allowed to leave.
Zia and her father (a brilliant scientist named Venn) lived in Caelondia, and in the dreams which tell the stories of the characters Zia meets a young man and tries to escape the city walls with him, but he betrays her and tells the authorities her father is using her as a spy to sell Caelondian secrets to the Ura. In exchange for Zia's freedom her father agrees to work for the city's Mancers.
The Caelondian Mancers task her father to work on a weapon of mass destruction which would destroy his own people (Ura). He resents this and rigs the weapon to backfire on them but it ultimately causes the Calamity, destroying most of both civilizations; there are few survivors and everyone else is turned to ash.
It was Zia who sang the bitter song "Build That Wall" during the story, which was basically a war chant telling the Caelondians they better build that wall stronger because one day the Ura would destroy it and the refugees (like herself) would be free. As beautiful as it sounds the message is one of deep resentment.
Zulf was on a mission to form peace between the Ura and Caelondians, so there is also a lot of bitterness and resentment at what they did to the Ura, and also because the Calamity killed his lover. He wants revenge on the only thing left of Caelondia, the Bastion, which Caelondia built as a means to reverse time/mistakes or, as a last resort, for a mass evacuation of its people. The narrator helped build it, and most of the time while you are gone he is telling these stories to Zia.
In the end the narrator wants you to reverse time, all the mistakes, death and suffering, and take back the Calamity. So he tasks you with finding the cores the Bastion needs for power to do this, which were scattered in the Calamity. The areas are floating because the Calamity ripped the world apart and tossed the pieces into the heavens.
Zia wants to stay in the present and evacuate instead. She assumes that if you turn back time the Calamity will just happen again and everyone will have to relive it. It's your choice. She says that all her good memories are after the Calamity, not before. She doesn't want to lose her new found freedom.
Zulf is seen as a traitor by the Ura and they almost kill him at the end. If you take Zulf's body he lives and is shown sailing on the Bastion with everyone else, if you choose evacuation. If you leave him he is missing from the art work, presumably left to die. When you carry his body out the Ura attack you initially, but then, as a sign of respect for a Caelondian showing empathy for an Ura, they just watch you and allow you to leave. There is even a point where a single Ura archer tries to attack you during this and he is cut down by a higher ranking Ura.
If you take Zulf and choose restoration he is shown being with his lover again in the credits, the narrator is shown by the monument working on the Bastion again (with the squirts being docile again), and Zia alone and sad at once again being a prisoner of the city walls -- looks like she's playing her harp and singing Build That Wall. You can see these photos in the top screenshot of my last post.
The kid's story is less interesting and told during the Kid's dream if you want to know more about it. He worked building the wall and sent money home to his mother.
