First, all of Xaltotun's (please excuse any misspelling) ideas are good (i.e. I agree with them, ergo...).
Now a few of my own:
Fantasy world (e.g. elves, dwarves, orcs...) not post apocalyptical medieval world.
Real differences between 'races' and 'factions'.
World Creation: more sliders (% land, resource rareness (possibly beyond the current 'extraordinarily few to none at all' range), terrain types(?), roaming monster frequency, etc
Sovereign creation: you pick the point total available; AI gets that value +/- a value dependent on a difficulty (i.e. handicap or cheat)
Wealth: something beyond the current token gold mine and 12 guys named Viy. Taxes won't really work since you need to balance that with (un)happiness, which doesn't exist in the grey world of (select randomly generated sequence of 6-15 letters here). Lack of money is the key tedium generator in the current game. Caravans generating gold is good - sadly the population will all have starved to death before the caravan arrives.
Names: a little more variety in the names of champions. I really do have 9 guys named Viy in my current game.
Adventure Techs - some really should generate a random number of random resources. Within the area you have explored excluding AI ZoCs. Not a gold mine or a bee hive and an apple tree.
Diplomacy: a functional system
Dynasty: I marry off my daughters - what do I get in exchange (nothing, as far as I can tell). Don't say diplomacy benefits until that bit functions (my perceived value '29'; his '18 bazillion').
Magic 'Mana Pool': MoM is an excellent model, global mana pool, available to all (usable amount is minimum of global amount and spellcaster's 'essence rating'). Would be nice to add 'mana nodes' to shards as sources of said mana. Also potential sources from buildings, etc
Make water meaningful: fish, warships, whatever. Historically port cities have always been important; Elemental - waste of time.
More Lvl1 quests. Some pre-existing dungeons/nodes/ruins/etc from the start of the game. All inhabited by monsters, some easy, some butt kickers until the late game. Rewards commensurate with difficulty (gold, mana, magic items, spells)
Ability to convert resources to gold. Or do a much better job of balancing resources: 4000 materials, 1200 metal, 120 gold: what's wrong with this picture?
Tech tree: Lvl 1 techs should be lvl 1 techs. If it takes 10 turns when I have 1 research point, it shouldn't take 12 turns when I have 24 points 150 turns later. The overall pace of R&D is fine, just differentiate between tech levels (not all, e.g., Tech 1 levels have to cost the same but the cost should be fixed not variable).
Tactical combat - monsters could also come in squads (at least the human ones). Spawning groups of, e.g. goblins, orcs, whatever would also be nice.