The units you have must fight monsters all the time and level up. Fight only battles you will win with hardly any losses. 

Try Umber

I do fight as much as I can early on. I try to keep one full army with my SOV clearing my territory, and at least 2-3 defending units in each city. I usually put my extra champion in the newest city to help it grow faster.

But then comes the enemy with several armies, with 4-6 stacks of troops. I'm not even sure how they afford that. The only limit I have when growing my army is running out of money.

Also, random question, whats the point of border villages? The mercs they spawn cost like 2.2 gold/season, its crazy for how weak those units are. Worse, my last game I captured 2 of them and I couldn't destroy or drop the improvement (not even in city management screen).

The power level seems to be much more influenced by quantity of troops, and not quality, thought I could be wrong.

a simple change that can make the game a bit easier: add some extra AI factions above the recommended number. the recommended number is fairly low, so the AI factions can expand a lot and become powerful. if there are some more AI on a map, they clash sooner and may also start fighting among each other more frequently. 

diplomacy wise, it can be helpful to get trade agreements, economic agreements and non aggression pacts as soon as you meet them (assuming at this stage of the game they are about on par with you - if they are ahead of you, they will demand a lot of gold for the treaties). try to befriend at least the Ai that are on your side (if you are kingdom, make friends with kingdoms and vice versa) - you get a small positive diplo modifier for being on the same alignment, so make use of it before the small modifier gets overshadowed by other modifiers such as "you are weaker than us". i often invest most of my excess gold  in the early / mid game in economic and trade treaties (AI always charge you some 30-40g for the treaties). the nice thing about trade agreements is that each of them gives you 10% gildar bonus, so if you sign some treaties, this can turn your economy from "barely able to sustain my 5 spearmen units" to "field such a large army that AI offer me tribute / pay large sums for a non aggression pact" (at least up to and including hard difficulty, i haven't played expert or higher yet)

regarding the wonders: even if you don't get them, it's not such a huge loss. 25% extra production and food in your main production center is nice, but the long build time is also a large opportunity cost. in the same timeframe, you could probably build up all the low tech military infrastructure and build up a small but powerful army to clear strong/deadly lairs that block your further expansion (and get some level ups for your main hero in the process) - being able to field a competent army and expand into the regions they guarded (which are often high quality tiles such as 4/3/2 or 3/3/3) can be more valuable than a 25% production/growth boost in a single city.

plus- if you don't build them, someone else will, so you can still conquer them later when you are bigger and more powerful than your neighbor who invested all those production points in a wonder instead of expanding.

it's basically the same logic as it's always been in the civ series - wonders are cool and every player has the urge to build them, but the more experienced you get at the game, the more you realize that they are a trap and that you should really weigh the pros and cons before investing a large portion of your production - the "great axe rider stack of doom" is often a better early wonder than the great mill

The AI isn't necessarily building huge armies to gain high power ratings. Militia counts toward your power rating, the AI spams cities, and there's currently a bug where you'll get way more militia/catapults/guardians/imps in your city than you are supposed to. I recently had a game where Gilden was really high on the power rating for a while, I didn't have his lands scouted so I assumed he was going to be the big player in the game. Eventually he declared war on me because I was so "weak," I took out a couple mostly undefended cities, found one of his big cities, went into battle against like 30 guardian statues/idols, won without loses somehow, his power rating from me hitting that city dropped by 300 points and he was suddenly one of the lower ranked factions. He only had one other city, his capitol. So it was this piss weak faction with inflated ratings due to a bug.

The AI doesn't consider monsters a threat and doesn't factor them into their expansion plans. They push blindly and recklessly into monster territory, but the monsters don't ignore them, sometimes their risk backfires and they lose those new cities, other times they get lucky and the monsters don't attack and wander away. Monsters in general don't hit cities that often, so if you build a city next to a lair there's only a small chance that monster will attack that city. You as a player usually aren't going to take that risk, but the AIs always do. Add to that the militia multiplication bug and even if the monster does hit an AI city there's a good chance they have an abundance of defenders to beat it back.

Don't panic about power too much.  Making gildar should be your main concern.  Once you have a healthy income you can build up your army quickly.

Design cheap units and crank them out from a fortress.  I tend to go for something like these:

Spear Partisan

• Leather Armour
• Spear
• Acrobat
• Underdog

Axe Partisan

• Leather Armour
• Axe
• Wooden Shield
• Acrobat
• Underdog

The +3 Attack against higher-level units works great because these units don't have a lot of Defence so they have a high mortality rate and usually stay at a lower level than the enemies you will fight early on.  If they do somehow get to a high level, they have more hitpoints and more Dodge (from Acrobat trait) so they're useful for filling out the ranks of any army, even if they don't get their +3 Attack very regularly any more.

If your Fortress has a good Production rate you may find that these units pop out very quickly (depending on game setup).  Their wages are about 1.2 gildar per turn.

Don't be too bothered about the AI, unless you know you can take them in a fight.  Focus on clearing monster lairs and getting one of your champions (or your sovereign) levelled up so they can be useful.  Clearing lairs means the monsters never spawn again, which means the earlier you do them the less chance of them spitting out a really difficult group of monsters that will wipe the floor with your current troops.

In LH, when you've researched Cooperation, you can upgrade your 3-man groups to four men (for a price, naturally).  So if you have the money you would be crazy not to go for it early on if you can, one of the reasons the AI power level spikes is because they do these upgrades and instantly have more powerful units and armies.

I am sure. If you turn up monster density and world difficulty you will occasionally even see AIs destroyed by monsters, and wandering around the map you will see dead-end roads all over that used to be cities, razed by monsters. If you go further and increase monster density even more in the game files then monsters will just annihilate every AI rather quickly, you can win the game just by staying alive long enough. They are most definitely not ignored by or immune to monsters.

Quendar based factions are great since slaves are super cheap and don't cost maintenance.  The slave militia unit frequently can be built in 1 turn.  You can just spam huge groups of them and if they all die, so what?  It took as much time to build a whole group as it would take to build 1 normal unit. 

Here's a decent build.  If you think you know of anything better, i'd like to know. 

Enchanters, quick, master scouts, legacy of serrane, rebels

Sovereign:  Air disciple, fire disciple, brilliant, clumsy, i forgot the profession (probably warlock). 

Ditch the start weapon for a dagger that has +3 initiative, you only want the initiative bonus.  Pick mage, get fire tier 3, get the -1 casting time trait.

First champion goes mage as well, get the undead horde spell.  Get first champ a +2 or 3 initiative dagger if you can. 

Spam slave militia, until you can put a guy on a horse, then go for archery and put an archer on a horse.  Train enough normal units to fill out the sovereigns army.  Spam slave horse-archers all the time. 

Basically your 2 main heroes and your non-slave horse based units go in one group.  You can split the 2 heroes if you like.  Slave H-archers are for defense or random other heroes.  Watch your mana or you'll run out. 

Or just make a custom sovereign for any faction and pick the warlord profession. 

Well, swarming means that you really need numbers in your army.  And that's exactly what you don't have early on, unless you can squeeze some Militia or Spearmen in there.

Even then, casualties or even just injuries due to swarming mean you will need reinforcements often.

On the plus side, if you can weather the initial assault you can swarm with your own troops and annihilate enemies that would otherwise crush you.

Build more cities. Everything is a function of city count. 

As a side note:

Don't play on small map, "ravaged" terrain,  there are few city spots.

If you are not Quendar, and need cheap, quick-to-produce units, try this:

Go into design units, edit the scout. Remove the scout trait, whatever it is called. You'll have a unit with just the "weak" trait, and two-handed pole (which has no labor cost). Save the unit, call it "Peasant" or "Goons," whatever.

This unit can be built in usually 2-4 turns, and requires almost no wage (.2 I think). Use it to swell your armies to full strength, relying on swarm bonuses to kill things. They'll die frequently, but they are easily rebuilt.

This will swell your faction power, and  help your heroes to start leveling.