Challenging:
Found a city.
Murder any beasties nearby by means of magic and mayhem. Grab any heroes. Sell any useless loot and rush build stuff in the city. Build up Leather armor and spears, make a few defensive forces.
Tech-wise: Standing army, leatherworkings, some basic civ techs, and then we expand further. And Shard Harvesting.
Once the countryside is semi-safe, poineers are dropped to take important resources with outpost. The sovereign goes off and try to find a second spot to build a city. If she does, a city gets constructed. Upgrade to 5-man armies ASAP, get Bows ASAP. Bloodthirsty and Accuracy do the trick. +1 Army size.Make two more cities, exterminate the countryside a bit futher, if no kingdoms have come forth to uhm, share their lands, scout their lands, pick one and start a fight. Take over their cities. Wait till population reaches a decent level, pick a fight with the next kingdom. Exterminate, wait till population reaches a decent level, pick a fight with everyone else there is left. I always make sure I am about bankrupt... if I have cash, I spend it, aggressively.
Army-wise: Caster hero, 4-5 archers, 2 melee units (more archers if more room). Soon as chainmail has been discovered we deck out our archers in chainmail. Or platemail. Dont bother with leather.Heros primarily take traits that benefit the whole army like +1 iniative or healer, and caster traits.
Soon as I hit the 4-city stage, its effectively game over.... all I have to do is order my armies to wipe them out, all of them. If I cannot conquer areas, I will send specialists to raze the countryside ( 6-move scouts with shortbows do the trick....fast moving, hard to catch and very, very frustrating to fight...).
I prefer 3-move archers... move 2 spaces back, fire arrows. Rinse and repeat and make the enemy pay for every square they have to move.
Of course, specialist forces apply where needed. +Strength warriors with 2-handed axes, speedy spear-armed horsemen, horsearchers, it all depends on the oppostion.