The new KB maybe is better than 3, but if you're looking to play a Heroes game, it's not. It's an rpg with an army instead of a character.
As for the differences between the versions, 5 is basically 3, with even less balance between the sides, and 3d graphics that get in the way as much as they help. It's completely devoid of the charm the rest of the series has, going for a darker picture, and lacks adequate space on the tactical maps to do a lot with the armies. They do have magic versus might more balanced. If you play 3, you'll soon find that might either hits fast, or dies horribly.
4... All potential, no class. 3DO was going under when they released it early as a last ditch effort to stay afloat. It's very poorly balanced, the heroes go from massively powerful to nearly worthless, and they drop like flies early on while being all but invincible by the end of the game. You can win the campaigns by just having all hero armies after they gain the experience off the first couple maps. Vampires are so hard to kill that you guarantee defeat if you let a necro get too many of them, I've even lost to the AI because I couldn't get rid of them, and the AI is even worse than it is in 5. They have some very nice improvements, like caravans, but it's visibly unfinished.
Some people have said the campaigns in 5 are good, but I'm just not grasping that one. Story maybe, but they're almost entirely script driven. The AI is utterly incompetent, and you win or lose depending on how bad you suck. If it takes you two weeks to run across a map because you suck, you'll survive the two weeks worth army that hits when you get there. If you do it in one, you get butchered. If you spend a month dicking around, it's not even a nuisance. They're a little slow in 3, but at least they aren't just scripted encounters that reward playing like crap and penalize playing well. The best campaign is 2, but it's seriously old school, and seriously unbalanced.
Personal preference, H3 complete, but H5 does flow a little better for multiplayer games.