The AI SURPRISE!
We all know in most every game that ai is usually a pushover and we get so strong it becomes not much fun to continue on and boring.
So I propose the AI SURPRISE programming that knows when the game has reached that point. The AI surprise is about LUCK and there should be LUCk in this game. From out of nowhere the AI will get this LUCK and will be granted an X number of the most powerful creatures in the game that it can control (but at least a stack full). It's like a one last stand of a full stack that can romp and rampage the human player at will until he/she can come up with a plan and idea to defeat this monstrous stack of evil. (think of the Golden Horde Invasion of MTW) It should have teleport ability and/or flying. It should be rendered with several magical abilities for protection and/or offense or both. It should be so powerful the human players should go "oh sh*t where did he get all that sh*t"
Nothing I love more than to hear players complain about the ai cheating. lol Because it's quite alright for them to use every exploit in the book but if the ai gets one thing out of whack it's CHEATING LIKE A SOMBIATCH. lol
Now before you whine and wahaa Medieval Total War the first one actually has this feature. It is after you have destroyed a faction that it will return and when it does man oh mercy it returns with some very powerful units and usually a stack of them. I always loved this feature in MTW even though plenty of times it stomped me back and took several of my conquests it was still fun and challenging and of course the first time It happened quite a SURPRISE.