I played this shortly after it came out. I love HOMM style games, and the opportunity to play an updated version of the original King's Bounty game was too good to pass up. Unfortunately, I ran into some balancing issues. From what I understand from reading other boards, if you picked a certain class (I think it was warrior), it was playing the game on really hard mode, but another class (mage, I want to say) was extremely easy. I don't remember the details off the top of my head. My question is, were these issues every addressed?
About six months ago, I played the follow up, Armored Princess. That game was extremely unbalanced, but in a different way. In that game, the monsters would increase in sheer numbers/levels faster than you could gain levels/leadership, etc. I spoke to several hard core HOMM gamers just to make sure I was not missing some critical strategy. My friends pointed out that they had the same issues, and one of them informed me that on the main website for the game, there was a direct link to the cheat codes. It's almost as if the developers KNEW we'd have problems getting through the game (even on easy) and therefore put the codes on the front page.
What are your experiences?

I've only played the first game as a warrior (normal difficulty), so I can't speak to how it compares with the mage or paladin, but I can't say it was Really Hard. I did make extensive use of magic to supplement my troops, so maybe having more powerful magic would have made the game easier, but I was still able to finish many, many battles with few or no net casualties.
How far did you get? I'm currently playing Armored Princess as a warrior on normal difficulty. I'm up to level 34, and although I've always had to watch myself as I explore and fight, I've never hit a wall. The game does essentially leave it up to you to manage your own advancement - monsters do increase in level and difficulty rapidly as you discover new islands, and you have to determine what areas you can tackle and what areas you need to stay away from. The level ranges of the islands are broad and overlap with each other, so expect to do some backtracking. You'll also find many quests that are far too difficult at your current level - just file them away and come back later.
It's more demanding than the first game, I think, but it's really not that bad.

"It's more demanding than the first game, I think, but it's really not that bad."
Oh, it's a LOT more demanding. Now, they could have patched it since then (one would think it would be easy to fix.) But when I was playing it after release, it was really bad. I was about lv 15-20. I was using every trick in the book (dragon, spells, fresh troops, etc) and just kept getting my tail kicked. Mind you, I'm no novice, as I've played every HOMM game that's come out over the last decade or so. And, yes, I traveled to different islands, knowing that I was going to have to leave tougher stuff until later. The problem was that the five or so islands I had access to, at the time, all had "Impossible" level monsters (that's what it would say when I mouse'd over them). One of my freinds told me that picking mage was also a mistake because they were weaker than paladin, I believe.
To tell you how determined I was, I restarted (after reaching lv 15 or so) and tried again. On my second attempt, I made sure to play battles over and over (when necessary) to insure that I did not lose troops. Not only did that save me money, but it also gave me the perk that gives you more leadership or something if you go X battles w/o losses. Yet, in the end, the challenge curve exceeded my character's ability to keep up. I wound up in the same position where I traveled from island to island only to no longer have any more stacks of enemies that were less than "impossible" when I mouse'd over them.

I've had my copy since release, as well, still unpatched, and I haven't had nearly that kind of trouble. Even now, I can still find yellow and orange armies to fight, which in most cases aren't a severe threat. Are you sure you haven't missed a navigation chart somewhere? Maybe there's a random element to which islands you uncover, or how they're populated, that can cause problems.
On the matter of that, which islands have you discovered? I'm looking at my map now. At level 34, I think I have all but one of the islands discovered, and I've cleared Debir, Scarlet Wind, Rusty Anchor, and Bolo. I've also cleared most of Tekron, Mentero and Verona, except for a few high-level lairs. I'm exploring Elon now, and most of the overland monster groups con "equal in strength" (there's one "lethal" hero wandering around). There are three other small islands that I've only poked around on yet, and haven't visited in some time - they're likely closer to my level by now. I haven't visited the last two yet.

On both run throughs, I was around lv 20. I only uncovered 4 islands. I couldn't find another navigation chart either. And it wasn't just me. Both me and another person (who are both staff writers on a game site), as well as a number of people on an unrelated forum, were sharing the same issue. Perhaps, with all the random elements in the game, the experience can greatly vary from person to person and playthrough to playthrough.
Again, I found it ironic that they put the cheat codes on their front page :) With that being said, I'll give it another shot sometime soon.

I've found that playing a mage in Armored Princess requires quite a bit more finesse than in The Legend. In The Legend a mage could pretty much just nuke half the enemy army with their opening barrage, then let the troops easily handle mop-up. For the early and mid game of Armored Princess mages can't deal out nearly enough damage with spells to make a constant barrage of direct-damage spells worthwhile, and instead need to focus on using spells to control the shape of the battlefield. Slow, Fear, and Trap should be spells you become intimately acquainted with as they are very effective for controlling the advance of enemy units, and Fear is especially good for knocking large stacks of level 1-2 creatures completely out of the battle (provided you keep an army composed of level 3+ creatures). And once you get a few levels in the Trapper perk an enemy advance can be almost completely halted without you evening having to lift a finger. Also, Oil Mist is particularly good for neutralizing enemy archers for at least the first turn, which gives your own archers a chance to thin their ranks before you start taking damage from them. Resistances also play a much more significant role in Armored Princess than in The Legend, and in many battles you'll find that you can't hold the enemy completely off and need one or two units to slug it out; in these cases the likes of Guardmen, Horsemen, Knights, and Paladins coupled with Stoneskin can be veritable tanks (as you can boost up their physical damage resistance to >70%).
The main challenge with playing a mage, and you seem to have run into it, is the inherently low leadership of the class, so you'll want to grab anything you can to boost that up, whether it be artifacts, a companion (Jimmy+Blood of the Goddess), or several levels of the Grand Strategy perk. You can also bolster your ranks with disposable summoned units that can be used as throwaway meat shields (Royal Griffins are great for this). It's also important to get the most damage out of your troops as possible, so actively boosting moral, crit. chance, and getting your units extra turns also really helps (Paladins are great for this, and Assassins can be pretty good as well). It's also tougher to build up a large mana pool in Armored Princess, but the Transmute skill does a great job offsetting this, as at level 3 it means +10 mana every time you take out an enemy stack. I've played the game through twice with a mage (normal difficulty), and while it requires different tactics from The Legend along with greater overall strategic planning the difficulty actually isn't too bad as long as you keep these things in mind.

Yeah, I did just about all of those things. I've been playing these games for years. Granted, I don't expect to have to pull out ALL the stops just to survive when I'm playing the game on Normal / Average difficulty.
Reading that you guys got through the whole game without too much problem tells me that it was either patched, my professional co-gamers and I are just total novice noobz and shouldn't be writing about games, or that the randomizer element of AP somehow screwed us over on our games. (such as putting a critical navigation map in a difficult location or something).
My main problem was after clearing out the fourth or so island of all beatable monsters, I just ran out of things I could actually kill and no more islands to explore to build up even further. All the monster stacks said "impossible" at that point. I could beat anything less than that with no issue just using proper tactics and strategy.

So, I've been playing Armored Princess off and on for about six months (it's a good game to play that way), and over the past week, I finally felt the urge to complete it. Here's my final report on my first playthrough.
As I said, I played as a warrior. As it turns out, the spot where I left off (level 34 in Elon) had pretty much put me over the hump of the difficulty curve. Once I reached the mid-30s, the rest of the game only got easier. I was able to largely sweep the rest of the world, levelling up quickly and even killing "invincible" heroes with little difficulty. I actually skipped the nameless island entirely. The final boss wasn't too much of a challenge.
My army was pretty straightforward: knights, paladins, horsemen, hunters, inquisitors. Admittedly, I was probably fairly lucky with equipment, given my playstyle.
If I'm reading you correctly, you cleared out the first four islands of all but "invincible" armies, and had no other islands to visit at all? It doesn't surprise me that there were a few invincibles left (probably heroes or stacks guarding a map), but I would have expected that you would have found another island by that point. I think I had uncovered at least Tekron and Montero by the time I finished the four newbie islands, though I had to pick my way through and avoid the tougher stacks at first.
It seems most likely that there was a necessary nav chart you hadn't claimed, either because you overlooked it or because it was guarded by a difficult monster stack, but it seems very strange that that would happen twice at the same point in the game. Without actually loading your saved game myself, I can only speculate.
Were you playing the North American launch version? The game has been patched since its original Russian release (to what effect, I don't know), but the North American version launched at 1.2 and hasn't seen any further patches.

I've played all the homm and the original KB but I can assure you I'm no expert. I played the original game through once as a warrior once as a mage. Mage was easier just blast fire spells so it got very boring.
Armored Princess I played through once as a warrior. I wasn't afraid to die and go back to the castle. Once I got through the early game it was pretty smooth sailing, and I had no problem finding enough islands of appropriate level.
I used normal difficulty for all playthroughs.

I tried it for a bit a while ago (don't remember if it was Legend or AP though) and eventually gave up, because yes, it is a bit weak.

I haven't tried it. If I remember right the Paladin advantages are tremendous damage against undead and oodles of cash. At least that's how it looked in the first game. Maybe I should give it a whirl in AP.

I played a paladin my first time through, and it did feel a bit underpowered. They get some bonuses against demons and undead, but it really didn't seem to make much of a difference to me. Basically it just struck me as being a class for those who wanted to sit on the fence between warrior and mage, without having the full bonuses of either (I think it was a bit telling that one of the paladin-only skills was just an exchange of mind runes for might and magic runes).

I don't like to resurrect old threads, but I'd thought that I would share something with y'all. According to one of the staff members on RPGamer, the new expansion for Kings Bounty: Armored Princess not only adds on a bunch of content, but directly addresses the balancing issues we were discussing here. So check it out!