[thejeff]

Victory Conditions.

Don't try playing a 600 province game with all nations in it. You'll be massively dominant long before actually taking all the provinces.

I usually play with 5-6 nations, 10-15 provinces each. 10%+1 capitals as a victory condition. You don't really get into endgame magic, but the AI can't handle that anyway.
Early/midgame is where the AI works best.

And don't recruit troops in every province anyway. Recruit troops in the castles near the front and maybe capital only troops. (And your occasional good indy province) Recruit mages everywhere you can. You should be spending most of your money on mages by the time you've got 50 provinces.