[Nick_K]

I believe you can setup pretenders in map files, although I've never tried anything like it. Presumably high-difficulty AIs with custom pretencders could be created that way. I still think that giving the human a bad setup might be easier though.

Improvements to the AI would be quite nice. Second to UI improvements IMO, but still quite important. We did see a big jump from doms2 to doms3. The AI is far more effective now.
AI coding is notoriously difficult for complex games and there are generally complaints about AIs for most strategy games. Things that seem obvious to a human can be very difficult to implement without adding new weaknesses for the computer player. There are very few games indeed which actually improve the AI at higher difficulty levels - unless the AI has been deliberately handicapped at lower ones (for instance, in HOMM4 the easy AI cannot use the 'wait' command in battles). Giving them bonuses and occasionally tweaks to aggression seem to be the way things are usually done. I wouldn't complain about the AI 'cheating'... anyway, it's hardly cheating if the human player has specifically requested a harder opponent.

I'd quite like to see some scenario-type map files that can challenge a human player... but most map files are quite large and I dislike playing anything much over 100 provinces so they probably wouldn't be for me.