I'll start by saying that this is a surprisingly good game, but one that I feel could be made into a truly great one if not for a couple very huge flaws, one of which is easily fixed and the one I'm going to be talking about here.
I'll mention this once more: this first flaw is not only huge, but easily fixed.
Personally, the one thing that annoys me the most, by far, is having to ride to creature dwellings to recruit them when you already have some in your army. Throughout the game you find flags, equip items that increase Leadership, get promotions, and of course lose creatures during battles.
The need to restock creatures is constant, and over the time I've played King's Bounty, several hours have been spent just riding around restocking.
Before someone mentions Reserves... there's only two Reserve slots, they need to be bought, and you may want to keep them to transport alternative creatures. There's even a couple special situations where you need to keep one open for "quest" creatures like, say, a cyclops for the magic school, or even just to hold your normal creatures while you feed venomous things to your swamp Spirit, or maybe hold Priests to upgrade because there's no more Inquisitors available in vendors.
Proposal: enable some option to hire creatures (assuming that you already have some of that exact type in your army, of course) from anywhere on the world map, for twice their normal hiring cost. This could also solve the problem of absurdly small creature availability (three Royal Thorns, four Arctic Bears, two Black Knights, etc. from some obscure vendors) without having to resort to the Sacrifice spell to "grow" those unit stacks, because that spell is too rare to rely upon and often will only be found halfway through the game. This is something that could be done with KB and AP with little difficulty.
Huge flaw, easy solution, immense game improvement.
A friend of mine also mentioned one flaw to me. He hasn't finished the game yet, but the thing he hates most is the totally random difficulty levels. When he tried doing the mage tower in Arlania and beating Enemen in the swamps, he faced a ridiculously powerful opponent without any warning whatsoever.
His suggestion was to balance things better, but in my opinion it would be sufficient to simply put a "suggested hero level" value on quests. That'd also be fairly easy to add, so I'm mentioning it here along with my own suggestion.
The other flaw of the game is, as many people have been complaining about, the absurd level of randomness when it comes to creature/item/spell generation. That however is not so easily fixed and so I'm not going to go into any detail. I will however mention that, yes, it's pretty ridiculous, and while I understand that most of the replay value relies on this very randomness, there would have been other ways to go about it. As things are now it's impossible to "plan" a character; completing a particular set is highly unlikely, and like most players I really don't like the game telling me what it wants me to be, especially based on some dumb random number generator.
So there you go. From my point of view KB is a good game that could easily be made into a great game, and the designers/developers knowing about the randomness issue just makes it possible to look forward to future games! Not that I'm not looking forward to AP already.