An AI built from scratch would be nice; with specific tactics and doctrines for factions (i.e. you wouldn't use the shield wall if you are Eastern European, Asian or Muslim factions).

Simply put an AI that is adaptable... I am sick and tired of being able to destroy an army piecemeal like William did the Anglo-Saxons at Hastings (though it should work at times). I'd also like to see the AI scaled, meaning if the enemy General has no command stars, the AI fights ineptly, but if the enemy general has full compliment of stars he kicks ass.

Moreover, aggressive AI for aggressive generals and a reserved AI for reserved generals, say Richard the Lionheart who was aggressive versus Saladin (who was much more reserved).

Simply put, I want an AI with few exploits, an AI that has a stored library of doctrine and tactics from which to draw upon, that will compare my force to his and act appropriately.

Moreover, I want an AI that can put me off balance. If I launch an attack from the campaign map, I pretty much know that the AI will not go on the offensive, and if the AI attacks me, I know the AI will be advancing.

Simply put, I want CA to stuff a general's brain inside the game somewhere...

Campaign wise, I want an AI that is not stupid. Example, I play the HRE, the French have been beaten by the English and have only one Territory left which borders me. I got two full stacks of troops bordering the French territory and the French are still facing off against the British. And then the French attack me...