How to make cities different from each other? I think there should be different development paths open for them. Instead of a library and barracks in every city, you'll have three different paths:
1) Might. This one will be what everyone expects - libraries, barracks, big population etc. Makes troops like spearmen, slingers and paladins armed with adamantium weapons. Researchs non-magical techs.
2) Magic. Magical tower, then magical stronghold and later a flying magical fortress. Researchs magic, makes troops like golems, phantom warriors and undead. Peasants don't like undead or flying fortresses so population is low.
3) Heroic. Frontier outpost, frontier castle and a meeting place for heroes and researchers of all supernatural, superfortress with an enormous extradimensional portal generator. Makes units like bear cavalry (domesticated monsters), attracts and trains heroes. People don't like wilderness around and portal generators are bad for health and crops so population is low too.
First and second choice is obvious so i'll focus on the third choice. (3) starts as a frontier outpost with available buildings like a tavern (attracts heroes) and say a soothsayer/prophet guild (to find quests and places of interest). Even if you don't have other heroes yet, you can get a quest for your Sovereign. It's a place with untamed wilds around so researchers start to gather around and found a sorcerer's guild.
Sorcery is like magic but it focuses on divination, summoning of magical beasts and dimensional travel. After a while, there is nothing left to explore nearby but with the newly researched dimensional travel and with the help of divination it's possible to find new places of interest for your heroes. Unfortunately, it requires mana to keep a living being in another dimension (so you need to pay mana upkeep for summoned monsters and this sorcery doesn't allow to colonize other dimensions) but it's good enough if you want to summmon magical monsters or send your heroes on a quest.
Victory conditions
Military conquest is possible either way, be it with adamantium-wielding paladins (might), army of undead or golems (magic) or super-powerful heroes (heroic).
Other than that, there are specific victory paths open to different development paths:
Might:
Diplomatic victory. Requires a lot of research in diplomacy, alliances, trade relations etc. Maybe some wonder too, like in Civ.
Magic:
Spell of Mastery. "Technological victory". Requires brand-new magical fortress to aid in casting.
Heroic:
"Ascension victory". Your sovereign becomes so strong that he reaches a higher state of enlgithment / goodhood / whatever.
"King of the hill deathmatch" Advances in sorcery allows your sovereign to break other sovereign's magical anti-scrying/anti-teleport defenses and with the help of a brand-new dimensional portal he pays them a visit. A bloody one, that is. Well, you may guess which victory condition i like the most 
***
Maybe some basic buildings may be allowed in any type of city, but you can build only one type of advanced building. That way, it will not be necessary to balance a starting build order in 3 cities.
***
Why i think the game will be more interesting that way
First, now you have at least 3 distinct types of cities instead of evertything being the same.
Second, i think heroes are left aside in many TBS and you can't do much with them. "Heroic" city will focus specifically on heroes.
Third, now you have a different development options depending on starting terrain. A lot of land and an iron in a starting city? Try the "Might" way (good for expansionists). Magical crystals lying around? "Magic" seems the right thing. Small isle with lots of ruins? "Heroic" way will be the best (you don't need a lot of land to succeed).
Fourth, with the right game mechanics (if it will be more efficient to specialize) cooperative multiplayer or team deathmatch multiplayer will be more interesting - instead of every player being the same, we may have 3 players specializing in different things.
