I've started playing this game some again after being away for a while, and in messing around some I've had to re-learn some things.
It sounds like you're taking too long to get your magic going. It seems like you have a plan to build up your empire, and then get into magic, but really you start researching magic almost right away. IMO part of the reason the AI is an easy opponent is because it rarely researches magic, and once you get Evocation 4-6 and a solid number of combat mages it's pretty easy to blow up a much larger army. (Everyone's mentioned EA Abysia,
I could've misread your description, though, but it sounds like you're following a plan of 'establish territory, then do magic', or 'get a feel for combat, then do magic', but IMO the magic system really is the heart of the game. When you feel like you have a handle on the game to play without getting stomped and want to mess around with magic, my EA Tien Chi game taught me a LOT about the magic system, and the use of different items/summons to do diversification. (Along with this:
http://strategywiki.org/wiki/Dominio...ing_and_Autumn).
I haven't played that many multiplayer games, but you can test out a lot of tricks against the AI. (You don't learn many counters against the ai, though, because it has basically one fighting style...I really wish I could get the AI to obligingly set up a large spell communion...)