I hate rushing, so usually play a loooong game. Starting with Sovereign creation, I like to have all 4 spellbooks, Have the trait that gives +2 mana, Going to try a few other Sov combinations to see how it affects the starting. Dont want to waste turns in the beginning, so plunk my settlement down near the fertile land preferably on the first turn, then buy travelling boots so I can travel further during turns. Equip janusk with boots too, then scout just a bit to get the nearby goodies (lucky if you get +10 materials early). Trojasman suggested building workshop first, as materials is *crucial* early on, then the beacon of Hope. Real exploration starts when settlment levels up to 2 and can get boar spear, to have a bit of attack, or the mosters just are too powerful early on. One thing happened to me, when the horde of spiders attacked, I just escaped and they didnt raze the settlement. Only when there was a bandit the settlement was razed when you ran away from the battle.
I like to give Gildar bonuses since the first settlement is usually going to level up to 5 first and its a Goldozer powerhouse. Even if there is a Lost Library nearby you wont be able to just click on it and build a library, first you have to have a tech library, unlock one Adventuring tech, then only you can build the Lost Library to get +5 tech.
By this time (I think 30 or so turns) I can build a pioneer, get second settlement (guarded by Hero with boar spear) and make it have Tech bonuses and build nothing but Tech Labs. Only then I start the next three settlements which all will get Arcane bonuses so I can research spells. Raise land, Lower Land, Teleport.. after a while Call to Arms, then Greater Grip of Winter. Unlock the magical books as per the shards I get. By this time (I think 120 turns or so) there is no way to lose with the current game..
By the way, I dont like to declare war till reaching 200+ turns, letting the AIs get powerful (my power rating is usually low, cause I dont train squads till much later, depending mostly on Heroes decked out with armor, and the Sovereign helping with spells) and it is usually they who declare war, after demanding a ransom or two.