I would like for the AI to play a consistent game and to stay in character. Some examples of what I mean by this:
* An AI that has been mainly using mounted units shouldn't all of a sudden switch to building only heavy infantry just because it's enemy has started deploying spearmen. It should look for other ways to deal with them; bring along a fireball casting hero, bring a monster that causes the enemy to break formation and flee so my cavalry can run them down, train mounted archers that stay out of reach of the spearmen, etc... This way an AI could specialise in a certain kind of warfare and therefore remain recognisable, rather than each AI becoming a generalist and almost indistinguishable from each other. (Ofcourse there should be some flexibility; if my army is fire immune and the AI has no way to remove that immunity it shouldn't keep summoning fire elementals just because that's what it has been doing in the past.)
* The AI shouldn't be always playing to 'win', especially when it has little chance of actually winning. For example if I'm at war with an empire and it looks like I might win, thereby becoming the dominant faction, smaller factions shouldn't declare war on me just to keep me from winning. Some factions, especially those that have no reason to hate me, should cut their losses and try to ally with me, choosing survival over victory. On the other hand, if I've betrayed allies in the past they might not trust me enough to do that.
* So a related point, AI's should remember my previous interactions with them and other AI's. If i've stabbed previous allies in the back, they don't trust me. If I'm known for helping out friends in need, they trust me more.
* Allow me to negotiate strategy with my allies during wars, like in Alpha Centauri. So setting specific targets for capture or defence, general strategy (defence, raiding, (re-)conquest), etc..
2) City building and management
* I would prefer cities to just occupy one tile, but if building on the main map is staying I hope cities won't become huge map covering blobs that they are in WoM.
* The switch to local food production is nice, but I hope this doesn't mean that every settlement eventually grows into a city.
* It would be nice if caravans could be used to transport excess food from one town to another, allowing towns to become feeder towns to larger cities.
* I would like buildings to be upgradeable, but only manually. WoM's automatic and free upgrade is just wrong on so many levels.
* Allow for more than one type of building to be build on a resource, and allow these buildings to be upgradeable as well.
* Allow heroes to become govenors of a city, having positive (and negative) effects on certain areas, depending on the hero.
3) The world map
* Allow 'wildlands' to remain a distinct area (with it's own rules) even after capturing it, rather than it becoming generic lands.
* Allow building structures like forts and watchtowers on the map, independent of cities and resources.
Just for the record, I would like to see actual siege battles (with walls), obstacles on the battlefield, zones of control, and allowing for maneuvers like flanking.