Indeed, on normal the game dose seem like its easy to steamroll the AI, but that is normal setting, and many of us have now been playing for many months, their is a large learning curve with EWOM, that I believe many of us may have forgotten, if normal becomes too hard, then the 4 levels above it become much harder, it seems a little change at the normal level = a massive change at the other end.
Their are many ways to make your game harder, you can change the AI of just one or two oponets, you can increase the worlds difficulty; you can even (and this is my preferred one) slow down you tech tree to epic levels, no one gets to quickly rolled then.
What I would like to see is rather then the AI getting massive hit points, and braking rules a change to the systems of the AI levels.
At normal everything runs the same for AI and human. As the levels goes up, all costs for the AI, all building times go down by 5 or 10%. All rolls in combat go up (or down which ever is best) by the same 5 or 10%. In the easy levels the reverse happens. This would also allow one basic AI file as the hardness would be handle by the system, not the AI, making the AI easer to code.