Brad wrote in another post,

"Players are very good at creating a very sharp tip to their spear. AIs, by contrast, are good at defense in depth. 
The general problem in FE, is that the current design gives a big advantage to the player with the sharpest spear and that's inevitably, the human player."

That set me off thinking about what kind of small-ish game design changes could result in large changes to the AI's ability to compete.  To get there, I started thinking about recent game experiences where the AI didn't succeed in a war with me in early, mid, or late game (I usually play on large maps with 8 AI's, Hard difficulty, so that's where these examples come from). 

The AI has gotten much better about having troops ready to attack before declaring war.  Each time, I had barely 2-3 turns to recall some defense before they entered my territory with anywhere from 5-10 stacks of max armies (5 units per army = max).  That's a pretty sharp tip, considering I had 2 max armies total if I pooled all my units everywhere.  And, when techs were available, they were mixed range & melee, so were very effective.  Each assault failed, mostly because:

They moved too slow - and I was able to react to them.  Even when there were roads, the pathfinding algorithm isn't good at using them, so they'd move 1 tile per turn across the rough terrain. When the player invades, you can bet he's taking a road that lets him hit the city in the first season of the war, second at the latest.

Possible game design changes (aside from fixing pathing) that might enable them to crush me better:

• Make the scout ability a spell that can be cast on an army so they can at least move 2 spaces per turn across rough terrain, and have the AI use this on invading armies (or just tireless march, or both!)

All their troops were level 1, or 2 in late game fights, while mine were level 5, 6, or higher early, and something like 10 or 11 later.  The HP difference between a level 1 unit and a level 6 unit is extreme and the AI armies could not overcome it.

Possible changes:

• Set a max level or a max hp for trained units to limit the player's ability to create a [trained] stack of doom
• Create more opportunities for the AI (and player to be fair) to level trained units
• Possibly a "Train" option for units in cities (with a barracks) - the unit becomes immobile for N turns and gains 10? 20? xp per turn.  The AI will be better about micromanaging this than the player, and it will let the AI's armies compete on more level footing.
• What is already being done - giving factions more powerful trained units (golems, spiders, juggernauts, etc).  Trained units at level 1 are chaff, but these special units start at higher levels.

They didn't have caster / champion support.  The one invasion that came close to succeeding had 2 champions at its helm - one crit'd my sovereign into oblivion then proceeded to trash 3 outposts before I brought up reserves and took him out.  If they hadn't "moved too slow" and skipped the road, my city would have been lost.  Other invasions frequently had zero or one champion

Possible changes:

• More champions - I see in the new patch notes that Altar can train henchmen - that's amazing, and has a lot of potential to increase the AI's capability if it had a caster with nearly every army.  If the AIs had access to more champions and the AI was set to put one champion with each army, they'd have significantly higher capability

Their cities fall like dominoes.  Only once, against Magnar's capitol in the early game, was I ever stymied trying to take an AI city.  They had their sovereign and 4 champions stationed (some immobile) there along with some ranged and some melee units, 9 units in total.  That's in my current game where my sovereign level 7 and is running around with 3 spearmen parties, and it's making the game a lot more fun. 

Possible changes (some of these aren't so minor):

• More magical city defense - I've mentioned this in another post, but low, mid, and high level spells with and without mana maintenance for city defense would make cities harder to take.  Maybe a level 1 earth spell to make a hedge wall around my town, a level 1 water spell to add a moat (slows attackers to speed 1), an air spell for a wall of lightning, something to beef up city defense in a hurry so the AI can react more quickly, and not just at fire level 3/4
• More mundane city defense - lots of people have had ideas on how to make cities hard points, I hope that's coming in Beta 4?
• Cities can rebel if you don't leave defenders.  That way, unless I prepare in advance, the army I just conquered the city with can't up and go the same turn, or even the next 5 turns, not without risking rebellion.

And I'm sure people can come up with more - what other fairly small changes to game design can help the AI out?