Just a piece of information about the Dominions AI. Beating 3 or 10 AIs in Dominions is not necessarily harder than beating just one. If you are lucky it will even be easier to beat 3 AIs than one. When you have more than one AI they will fight among themselves as well and that obviously weakens them.
Besides editing the .map file perhaps an option will exist to ally specific nations before a game starts.
Ideally the best feature we can hope for is some method where us gamers can modify/adjust the AI via scripting or another method. This will greatly open the door for more challenging AIs.