So hard! What am I doing wrong?

I dont know what you do wrong, but i still think the game is way to easy.

I play at normal difficult, Altair. Version 0.77

I start with using my soverign to explore the world, i dont fight anything yet till i found some basic equip. After this, its pretty easy, i get a level up every second fight. I mostly use my soverign + 1-2 heroes only and 4-5 troops and just steamroll anything

I think that Beginner should be much easier to allow players to do well without having to get frustrated for the first 5 games they play. 

Try switching to Challenging on a medium sized random map. That is what I play on and I am doing well. Also, Lord Verga is the best Sov to start out with. He is just so powerful. 

You should be getting all your armor from killing monsters, going on quests, and all the goodie huts. Try to make your Sov get as many movement upgrades from leveling as you can. Also, Initiative is what wins battles for Verga. Get it where you can.

Heroes are great because they open up the magic books for you. Imbue them as soon as possible. 

Food is the best resource in the game. Try to settle on a 5 or a 6. Production is less important. A 5/2 city will outproduce a 3/4 city rather quickly. Make sure you get your first city to level 3 before settling another. Use outposts (pioneers can also build these) to capture resources as soon as the game starts. You have to beat the AI to them or they will force you to declare war in order to get your Empire up and running. 

Civic techs are the most powerful in the early game. It's all about food and prestige. Leveling your Sov gives you more prestige too. Maybe get spears and use the trait shield wall to have a little defense. Then alternate pioneers and spearmen until you can unlock another food building. 

The game isn't perfect right now, but this is the best way to start. Hope something I said helps. 

It seems like they've toned down the number of available heroes.

So there is no point settling a city and producing troops early in the game? That seems very strange to me for a civ building game. Shame cos that's the way I like to play these games!

Couple thoughts.  The game got much harder on 0.76 than 0.75 because leveling heroes was slower.  I haven't tried 0.77 enough to evaluate it.  I've mostly been played on hard, but I think the general principles will hold for the other levels as well.

Some heroes are easier to play than others.  I think probably the most straightforward one to play is Magnar.  His fire magic hits hard and at a distance.  With Mangar you should be able to whittle enemies down to low level before they reach your hero.  When using Magnar at the start, he and your other heroes should retreat at the start of each turn and then have Magnar cast FireDart -- this gives the maximum number of casts before the enemy reaches your line.  You will need to what and have your mana supply recuperate between tough fights, although it won't necessarily take any longer than a fighter would need to recuperate to get his health back up.

Alternatively you can play a strong fighter.  I've only done custom fighters, but someone like Verga is probably your best bet.  (If you want to play Kingdom, simply custom recreate Magnar or Verga). 

Generally Sovereigns with non-direct attack magic are weaker in the early game, so you may want to avoid playing them until you've got more experience playing.  Although potentially Procipinee can be quite good if you can stack good enchanments on her.

Don't underestimate the importance of magic.  For example, if you can unlock the "Book of Winds" tech it's Obscuring Fog spell will help a lot.  Similarly Haste and Slow are both low level spells which can turn the tide in your favor when facing a tough battle.

You need to proceed cautiously.  Only take down enemies with low hit points until your heroes gain a few levels.  Don't proceed until your group is at full health, just sit tight until your health is back up.  You won't need to do this after you get up a few levels, but early on, you don't have a lot of health margin especially for level 1 heroes.

I've found in 0.76 some of the starting quests found at modest inns are actually to tough for starting heroes.  To get to the point where you can do these loot every treasure point you can find.  Good gear makes a big difference.  Take out as many single low-level monsters as you can.  One butcherman should be pretty easy -- a group of three butcherman is likely to be deadly.  Unfortunately under 0.76 it's tough leveling by killing these, but in addition to gaining a bit of XP they usually have a bit of gear which have a good chance of being useful to you.

Skirt tough enemies and go hunting for more heroes to hire.  Loot treasure as you go along.  If you're lucky you can get a band of 4-5 heroes and get them leveled up a bit and then come back and clear out those monsters that are preventing your settlement from expanding.

Creature AI is much more aggressive in .77, at least on Challenging difficulty.  This is hard to do!

Well pre-0.77 you definitely wanted to get that first city up and producing Gilars.  I haven't played with the new 0.77 Merchant nerf, but I unless I'm missing something, getting that city up is still critical, it's just going to take longer for it to really start bringing in cash.  Without cash you can't hire new heroes, and no new heroes is very bad news.  You basically want to get as many heroes as you can as fast as possible.  So yeah, definitely get a city up as quickly as you can.  Also you want to grab any resources you can with at least outposts, if not cities.  That goes double for any magic shards you find.

As far as troops go, generally I haven't bothered producing troops until I at least get Leather armor up, and that doesn't seem to have had that much of a negative impact.  We'll have to see what happens when the AI gets ramped up though.  Longer term though, yeah you need troops guarding your cities.  The militia by themselves aren't strong enough to protect against a determined push against your city.  Plus you'll need some sort of mobile force protecting against enemy empires and players raiding your territory and burning your mines, stables, and enchanged shards.

With the slower leveling of heroes in 0.76, it wouldn't surprise me if a spear unit or two helped make the exploration process easier.  Not sure with 0.77's readjustment of leveling (I haven't had a chance to try it).

Also you can create some pretty useful troops early on.  For example you can create a cheap scout unit that increases your army's movement and sight.  You can attack that scout to your hero stack and make it move across the map quicker.

The focus for the beginning is to level your Sov and get your capitol running. A regular army can be don, but you need to have a specific strategy that I can do, but not explain without a huge wall of text. This is why I think Beginner should make enemies much easier. You should be able to try out a regular army strategy there to perfect it and then move up in difficulty. The problem is that this is still early beta, so Warfare and Civilization are not well balanced. You do need a few food buildings to get things going. A level 5 city is the most viable early game strategy, but by release I doubt it will be the same case. Until then, you gotta report your balance issues in the support forum to make sure the devs see the problem. New players are very valuable as they bring in new perspectives. I notice you are of the first million users. Hard to believe any are still alive and testing. 

Sweet thanks for the info guys. Another example of the difficulty was that 'return the noble daughter home' quest. As much as I didn't want to be a prick, I had to sell her to the bandits cos they were just impossible for me to beat at low level.

Crown of Prociponee (or whatever it's called) + a sovereign with a few levels in a few magic skills = Instawins.

Haha, that's actually funny!  "Sorry woman, I don't have any money to get home.  Here you go fellas, how about 100 gildars?"