Not enough info to tell you what you did wrong, but if you're still fighting it, mobility has always been the AI's weakness. Use movement to avoid his huge army and take all weakly defended cities. Make fodder to weaken his remaining army and then finish him off.

Archers are always good.  A couple squads (or larger units) of longbows (no armor needed) can destroy most AI units I've run across especially if you have the crystal to pump them up with rings/amulets/etc... that boost attack 90+ ranged attack is so much fun.  Throw in a few Ice Lords or some other high attack melee unit for when things get close to you.  Always target anything with a ranged ability first and try to lure his melee units on to squares that don't give a defense bonus while you camp on squares that do.  And of course be the one to attack first.

it is most likely the case that your enemy ai had enough time to build grouped units - and grouped units are broken as hell (although apparently not as much as pioneers, organized, teleport, or arcane doom *rolls eyes*).

Currently, a unit which starts as a group (3, 4, 6, 8, 9, 12 fighters as 1 unit) retains it's entire attack and defensive strength no matter how much damage you do i=to it... so even if it's down to 1 guy out of the original 12, he still hits and defends like 12.

It makes them tremendously hard to kill, especially under the current combat hit/miss system  You need pretty much true-damage magic to make a dent in their hp (i've seen 120+ hp), and even that takes multiple turns when you had arcane doom + flame breath.  With flame breath alone... good luck.

Explore faster I'd say, you should atleast find your closest neighbours fairly fast. And then keep an eye on them. If you start getting negative multiplier, spam some squads of axe/shield men (or spearmen if you don't have metal) untill you are neutral again. Making units without armor doesn't cost that much and it does the trick till you can afford some more expensive units. the key is to start soon enough, before they are hostile to you.

Or if you are too late, you shouldn't have too much trouble taking them down with the correct spells and some archers if you have them. There's an air-spell that knocks back enemies while doing damage (can't remember the name). So you can easily avoid damage yourself by using deflect, hitting them a few times and then knock them back 2 squares so they have to run upto you again. It helps if you have a few more casters beside your sovereign though.