[LDiCesare]

UI:
Be able to iconify the information boxes (units, menus, province info... all). The list of commanders for instance may well hide just about all the map. Right now, I end up with a dead part of the screen between menus in the upper right part of my screen.

Single Player:
-The ai would be much more interesting if it built castles.
-Some diplomacy would be great in SP. Simple things like propose to attack someone, request a province, allow for taking of a province.
-Make sure the program remains usable for SP and hotseat. A client/server thingy like some people want should remain hidden if it is implemented.

Fog of war: Remember information about regions you used to see but no longer do. This information would ba tagged as 'old' somehow. Who owns the province, strength of the troops... Alternately, let the player write some info for each province and display it on the map as an additional map filter.

Getting rid of useless units and items noone ever uses. Does anyone build light cavalry? Or make them worth buying. Here, less units/spells/items could actually be a plus.

Raid command. If your army has a strategic move of 2, you could use it to raid the neighboring province (i.e. attack, loot and come back) rather than attack it really. It would act as a pillage command, but in the neighboring province. The units would have to fight the defense force with something like a 'hold 3 turns and flee' order. This could make light cavalry worth buying. Plus it would be nasty.

A national building and national troop unlocked when this is built. If you research one school (e.g. Construction for Ulm, Summonning for Ermor, Evocation for Marignon...) to level X(6?), you have the ability to build one special building (in only one province) which unlocks a new national troop. This building would cost gold and gems (most races) or gems only (Ermor?) or gold only (Ulm?). The available units could be built either normally or through an 'enter site' command from an appropriate commander, and be worth buying late in the game.

Make the Arena worth going into it. Gaining a cursed two handed weapon, however strong, is no excuse for risking the death of your commander. Winning should instead give a special ability as the hall of fame does, boost some stats, provide luck, or something worth having. Particularly when you run the risks of facing a diseased scout equipped with a half dozen cursed items.

Already stated by others, but I'll repeat them here anyway:
-Add an option to play where underwater areas are all or mostly barren.
-Tax management: Be able to precise a tax reduction per unrest formula and say which provinces it does NOT apply to. Formula would be something like reduce tax by (float) for every 1 unrestor (int) per 10 unrest.
-Save God.