I'll start an idea. I'm picturing that starting off, you are not alone. You create this city with a [brother/cousin/friend] and you two are working hard. Once you get to the point of adding a squad, naturally, your [brother/cousin/friend] takes the lead on it, and dies on the first battle. now your family (or friends) are unhappy with you. a couple avenues that were open to you for support (I.e. bonuses to help you early on) have closed their doors. Part of the story can be about re-opening those doors.
I like this idea itself very much. It might not be as novel but is good nonetheless from a city builder game's perspective.
Even though my own idea for this might also not be something unique but anyhow, lets see.
There is a military raid going on, and you're one of the soldiers (maybe the best killing machine as well) in this raid. The reasons for the raid are unclear but you being the ideal soldier just believe in carrying out your mission. Once you've killed them all and razed the city to the ground, you stand on one of the ruins of a building and look around admiring your yet another feat. Then you catch sight of a few disturbing scenes that instantly spark something inside you. Few ideas for those scenes can be :
1) A small girl, without a limb, sitting beside the dead body of her brother, and there are no human emotions coming out of her.
2) An old man trying to pick up pieces off the ground, looking for the remains of his home where it once used to be.
3) Fire rising out of a temple with a priest sitting outside praying for, maybe dead people or peace?
This should trigger a change in the soldier's outlook on things and he swears to do a full cycle from destroying cities to building them.
And that's when he walks off into the darkness, pledging that no more destruction. Rather amend for this by building a new city.