Without further ado:
1) More diplomacy options. Being able to give a city (BIG diplomacy boost) or a unit, or gift non-equipped items, asking to make peace with someone (right now you can only ask to start a war)
2) More map generation options - things like general shape of the landmass (for example - one big continent), quantitiy of water (for those who hate many huge lakes), rivers, mountains, chasms (god, I hate those!) or yes/no to big setpieces (that can take over half the friggin map)
3) More unit upgrade options - right now you can ONLY upgrade to the latest stuff. Even if you don't want to. I hate when the game forces it - "either upgrade the unit THIS way or you can't upgrade it at all!"
And there are plenty of situation where you would NOT want to go all-out. Let's say you lack the required recources to upgrade units to champion armor, but you can easily upgrade to plate. Tough luck! Let's say you like that soldiers cloak (+10 magic resist) and don't want to upgrade to a dragon cloak. Too bad again!
At the very least there should be a non-magical upgrade option (for using the best non-magical equipment). I may not have the crystals necessary to upgrade my defenders with Doom Hammer, but Mauls do 25 damage and cost no crystals. BUT WAIT! You can't upgrade sucka!!!!
4) AI enhancements. It could do with some improvements so it uses it's units more efficiently and doesn't cripple it's own economy.