Have you played the campaign game?  It's called a campaign, but really it's an expanded tutorial which allows you to get the basic concepts of the game without having a bunch of AI units breathing down your neck.

If you've played the campaign through a few times, then I would recommend starting a game on the "Easy" setting and making a custom Sovereign that is geared out for combat.  Put 15 points in STR, AG and Constitution (I think).  Lower everything else down to 5.  Then play the game focusing on nothing but fighting.  Ignore magic all together and only research Military.  The balance of the game is still being worked on, but until it gets adjusted playing a combat-only game is an easy way to walk all over the AI and roving monsters without too much challenge.

The only other advise I can give you is to make sure that every turn counts.  Make sure your build queues are full and your cities are always growing.  It doesn't matter if you only have 3 gold at the end of each turn, because there's no point in saving it up really.  Gold is meant to be spent growing your empire.  Play this way and at the end of 50 turns, gold won't be a problem!  You'll be able to get all the goodies from the merchant, and until you save up enough your over-muscled Soverign can still pound everybody with his s+5 spear.

Thanks for the tips guys, I started a new game and once again one of the AI players was head and shoulders above everyone else when it came to might. Luckily I managed to survive long enough to see that the reason for their high power rating was that they had boatloads of weak troops with heaps of armies running around with 800+ strength.

I remember some guy earlier talking about "glass cannons" so I designed a very heavy unit with 25 attack and 18 defence, I only managed to make two squads before I was attacked by an army with a rating of 856 (My two guys in a squad had a rating of 300 or so) and packed with troops. It turns out that my heavy units in squads are devastating, especially when I got them to defend in terrain that gave a 50% bonus to defence. Despite being heavily outnumbered these two squads managed to defeat a couple 800+ armies and after training more squads I eventually took down the enemy empire.

It seems quality really does win out over quantity. It was a pivotal battle, had my little two-squad "knights" failed, I would have lost the game for sure.