I'd start with the campaign map:

- I'd also like to see something that forces the AI to concentrate power. I'd like to face big stacks of top of the line units. Maybe a resource bonus on higher difficulty levels to help them pull this off.
- It would be nice if the AI learned a little from experience. After it has seen my all cav archer army for the 20th time, it should stop making armies that are 80% phalanx or eastern infantry.

These seem fairly easy, and bigger and better stacks would go a long way to overcome the battle map issues.

On the battle map:

Cav or cav archer dominated armies seem to be a serious problem for the AI. This can either be solved by beefing up the counter-units, increasing the upkeep cost of cav, or improving the battlefield AI. It would be nice if it would recognize "Hey, I'm up against an all cav-archer army" and adopt approprate tactics.