I'm a veteran Hereos of Might & Magic player but new to King's Bounty. What difficulty should I play on if I want a challenge?

Hard should give you a pretty good challenge.

I found the difficulty in The Legend a bit lopsided. I played on hard and the game was actually pretty easy up until Demonis (for maybe about 3/4 of the game) when it suddenly turned pretty difficult. So you might pick a too difficult difficulty and realize it only after playing 20-30 hours. : ) But if you don't mind restarting on an easier difficulty if you get screwed, then I'd recommend Impossible and see how it goes.

For me Crossworlds (the Orcs on the March campaign) seemed easier than Legend. The reason being that there were so many opportunities for summon spam. Your pet gets a summon ability, you have Demonologists, Rune Mages, Royal Griffins, Royal Thorns. Or at least I did, it varies. So this suited my playstyle. I quit playing with a bit less than half the islands unexplored because of too much King's Bounty.

No matter how easy the game seems, make sure you almost never lose gold in battles.