[Uh-Nu-Buh]

I think a couple of things would really help speed games up:
1. auto-search for scouts/spies
2. auto-search for mages scrying for magic sites
3. auto-search for mages wandering around looking for magic sites.
4. being able to direct an army/unit to an endpoint and having intelligeng path-finding. Right now you have to direct them 1-2 province at a time, turn by turn. Maybe it would weigh like this: first would be friendly provinces, second would be provinces with enough supply, third would be provinces with fast terrain (e.g. avoid swamps, mntns, etc.), fourth would be least number of provinces. You could check the path and change it afterwards.
5. if 4 is too complicated, then how about scripted orders--then you could just tell an army/unit: script--move prov1, prov2, prov3, prov4, prov5, end.
6. in fact, scripting would be awesome. You could tell one mage to forge item wine bag every other turn. You could tell another mage who has summon vine men via an item, to just summon vine men every turn. You could tell a fortress to recruit 1 mystic and 8 myrmidons each turn.

This would go a long way towards easing the administration of a huge empire. In my current game, I am taking 15-60 minutes to do all the minutia (tactics, logistics, strategy). Then, when I hit E it takes 5-10 minutes to think and resolve battles etc.. I have an Athlon 3400 with 2GB of ram, and it is churning!