Why story? The breakthough of SimCity was the concept of software as a toy. The user creates their own fun. In a more modern context, open things to the community by allowing them to write and share their own stories.

Anyone familiar with the history of Kerbal Space Program knows this issue. KSP's developers releases a "contracts" system that was essentially a random story teller. A few variables were randomly selected to generate a task. Of course many of the tasks ended up being ridiculous and they had to back-fill with a series of rules, but it is still rather silly. Then in a more recent update they allowed users to create "missions" and share them via steam (yawn). But this was layer atop the previous contracts scheme, resulting in a grinding mess that many/most players simply ignore. They instead play according to self-created story arcs and self-imposed rules.

SimCity did it best. Give the players the tools to play, but don't tell them how to play. Build a world full of towns and potential then let the players loose to explore and play how they want. Don't try to randomly build quests. Create the interface so that players can write and share their own storylines. I envision something more like OpenOblivion, aka Elder Scrolls with community-created quests/factions/stories.