I don't see how a story (good/bad) is going to have any impact on game play. I would like to see more character interaction and/or random events with npc's. Where not every npc can be hired, trusted, married. Interacting with npc's would be far more interesting than managing buildings in a city. Some npc's would bring you quests or want something in return for joining you.
Npc (I am my own man/women)
- each ncp would have their own likes/dislikes hidden (your empire/magic type/npc/npc type/your people/war/peace/other kingdoms/attracted/not-attracted/etc.).
- The more time you spend with an npc (fighting/adventure/quests completed) the more you would learn about your npc's, their likes/dislikes are revealed.
Npc actions (some npc's just can't be trusted)
- Treason/seduction/cheating/stealing(tech, spells, equipment)/assignation/npc runs off with your prince/princess/spouse/revolt/have a child with unwed princess/kidnap members of your royal family
- Image your spouse decides he/she likes an npc more then you and they take over a city and become a neutral kingdom while your out adventuring.
Npc (let's make a deal)
- Some npc's can to get you into trouble, I will help you today if your just do me one little favor.
- Give/trade resources/gold/map/tech/spell/equipment/etc. for a princess or if you kill another npc.
- What will you be willing to give an npc for a scroll with a secret spell or location of a treasure or location.
- Npc tries to sell you the location of where an sovereign is going to be or could be just a trap.
- where each npc has a loyalty rating to you and your empire, that can change depending on your actions and their likes/dislikes.
- Buying them new equipment will improve loyalty.
- Trusting them to send on adventures/quests would improve loyalty.
- Allow them to marry into to your royal family.
- Spending more time with your spouse/hiers.
- Install an npc with power/rank as the governor of a city
- Endow an ncp with a title (Duke/Duchess/Sir/lord/lady/etc.)
- Promote an npc as the head of your army or captan of the city guards, etc.