Majesty is one of my favorite games so I can't let it go ;) It seems you may have fallen into "choose your missions freely" trap so allow me to give you a few hints and comments:
- Majesty is a hard game, same missions very hard. No point to argue about it
- Northern expansion is only for people who already mastered
the base game so don't try to play it before finishing the original campaign. The beginner quest in Northern Expansion means it's the easiest mission from this expansion but still harder than 95% missions from the base game.
- Elven Treachery is a unlockable mission - you have to fulfill certain requirements before you can access it. And every enlockable mission is harder then the average from a particular group which means that this particular mission is the hardest one from advanced missions. So it's not a good idea to play it before finishing other advanced missions.
I'm aware it is difficult to know it beforehand but if you try to beat some missions "in wrong order" things can get downhill pretty fast. It's not the best way to design a game, I agree.
The thing you should learn first is advantages and disadvantages of certain heroes. You can't really pick them randomly, some missions are (almost) impossible to beat with particular heroes build while much easier if you pick the right one. The best part of the game is learning which heroes to hire in which mission. And believe me it's not as difficult as it may seem at the beginning. There are some well known tricks like:
- don't hire healers if you fight other heroes (they may heal your enemies too - they are pacifist)
- build Temple of Krypta if you are facing a lot of long range enemies (skeletons are almost immune to arrows so they will take down every archer)
- never hire wizards if you are facing vampires (magic mirror spell)
There are more advanced strategies but sharing them kills the fun you can have. But let me assure once again: it's not a blind process. You can really see what are advantages and disadvantages of every hero and with time you can use them efficiently. The best way to do it is replaying missions which you barely won. See if you can do it better, perhaps other choices of heroes will be better (or worse). This way you may learn the game and proceed with more difficult missions.