[Endoperez]

The important things to keep in mind, in the early game:
1) You need money, so you have to conquer provinces.

2) To conquer provinces, a combination of infantry, archers and/or magic support is best.
2.1) In the beginning, I usually buy as much cheap survivability (good prot, def, hp) as I can. As Ulm, I'd recruit cheaper shielded units, as Jotunheim (Iron Woods or Utgård) I'd recruit Vaetti and humans, as Abysia I'd recruit Humanbred, etc. Numbers are important.
2.2) If you can recruit archers, longbowmen or crossbowmen which only cost few resources, recruit lots of them. Massed ranged units of any kind are devastating.
2.3) Check your starting spells. Abysia starts with Flare - very good! Broken Empire starts with Body Ethereal - AoE 1 and a single mage gives you 5-9 ethereal legionaires.
2.3) In some cases, your pretender can be worth many, many archers. Fire 6 and Fire Darts is decent, and the higher the Fire, the more darts. Check out all spells up to second level of research, and see what would benefit your nation the most. If it is a summon, numbers are important, if it is a damage spell, preferably it should affect many creatures. Mind Burn is good, I use Reanimation, etc.
2.4) If you can, have a priest who can cast at least Sermon of Courage, preferably Fanaticism, with your initial army. Your Prophet can do it, always. If you don't have Holy 3 priest, your prophet is better than any of your priests anyway, so you can make your starting commander your prophet. If you do have holy 3 or 4 priest, make it your prophet. Usually this means you have to recruit it in the first turn.
2.5) Mercenaries can be the ultimate cannon fodder, or support your archers or even infantry to enable you to conquer tougher provinces faster. Always put them more forward than your own units if they are melee units, because they are less important than your own units in almost all cases.
2.6) There are some special strategies some nations can utilize. E.g. C'tis Empoisoners can assassinate most indie commanders, especially with the help of Reanimate Skeleton, or if they manage to cast Hand of Death, or poison him. Elephants coupled with high-morale units also work well. They are Hypaspists for Arcoscephale, Wingless for Caelum.

3) You need to have enough starting dominion to not have to build temples in the early game. 5 is a bit low, but 7 is enough in most cases. I'd only go above 7 if my nation needed it for some special reason, like spreading the extreme temperature (Caelum), creating armies (Carrion Woods Pangaea) or spreading diseases to my enemies (Miasma C'tis).

4) Decide what you want to research. If you have lots of Astral 2 mages and some access to Astral 3, Thaumaturgy and Mind Burn, then Paralyze against big enemies, then Soul Slay, then Enslave Mind is good. If you have Water, Thaumaturgy has Sailors' Death. Evocation has lots of combat spells. Conjuration helps many nations, but especially Vinemen and Vine Ogres are used. Enchantment has lots of Death summons, and Raise Dead -combat spell can be massed to create enough undead to destroy more permanent armies. Construction helps in many things, especially once you get Construction 4. N2 -> Thistle Mace, E2 -> Earth Boots, etc. Vine Crown also helps your Vine summoners, so investing those is a good idea.

5) I think research is more important than site-searching, in the early game. I usually send only one or two mages searching, although other is usually one of my powerful ones if I can afford not researching with him and he's not in a danger. Farmlands have few sites, Forests and Mountains somewhat more, Wastelands many more sites. There are more Nature sites in Forests and Farmlands, Earth sites in Mountains, etc. Level 2 gives you most sites of a spesific tpye, and 3 virtually all of them. Level 4 sites are very rare. If you want to experiment with sites, choose a rainbow mage, and take level 2 in all paths your nation doesn't have EXCEPT Blood. While the few Blood sites are good, they are very rare.