I've loved the various HOMM that I've played, even though I'm not very good at high difficuty campaigns. I've also loved Disciples, that I've replayed a lot, playing different races. I've stopped playing because it got linked to bad memories (a beloved granduncle went terminally ill in a period where I was playing the undead campaign, so the iconography of barren landscapes taking over the world progressively felt a bit too symbolic for that time). Anyway :

I liked the mix of turn-based exploration, vaguely chess-like combats, and city building. I also liked the fairy-talish setting of HOMM (reminding me sometimes of medieval arthurian novels), but also the gorgeous sceneries of Disciples. I now realise there's a few games based on the same principles. I had not heard of them. "Age of Wonders", for instance ?

Could people who have played them try to pinpoint the differences between these similar franchises, and suggest games based on the same sort of gameplay ?

There's King's Bounty. It's HOMM sans the city building aspect - Each settlement can sell you a limited amount of certain creatures, you can't choose the creatures or make the settlement grow. It is very good though the lack of restocking armies make the game much harder - Each combat counts and you'll want to finish each of them with the lowest amount of casualties possible.

Age of Wonders is a bit less focused on city building, the meat of the game is focused on overworld map army movement, but it is still relatively similar in style to HoMM, so if you love that series, then I would really recommend that you give AoW a shot.
One thing to note about the combat is that it is a bit more "open", you have a large playing area that you move your troops on, rather than the strict hex or grid based movement of the HoMM series. The magic system is a bit deeper in AoW than in HoMM, and there are a lot of pretty interesting spells to chose from, and AoW 1 also has a pretty deep hero leveling system.. Overall, AoW 1 is my personal favourite when it comes to games of this particular style, though the later games are also very good.

If the main draw of HoMM is the combat, then you have to check out King's Bounty. KB is a bit more of a CRPG with HoMM style combat than a pure strategy game, but it is pretty fun, and the shear amount of different creatures that you can have in your army, combined with how different they force you to play make the King's Bounty series really good.

"Master of Magic" (available on GOG) is a great game, if you can look past the pixelated graphics and not-so-bright AI.

"Age of Wonders", "Disciples", and "King's Bounty" have already been mentioned.

Oh, and I also forgot Lords of Magic (can be found here). While I found the enemy turns to take too much time (back when the game was still new, and I was using a P1 166mhz, so that might have been the issue). It plays a bit like a mix between Age of Wonders & Lords of the Realm.

And the reason King's Bounty is so similar is that it's a modern remake of the original King's Bounty, which was pretty much Heroes of Might and Magic 0.

I've heard the Warlords games are kind of like HoMM but I've never played them. Maybe someone else can comment.

I think this is the series:
http://www.mobygames.com/game-group/warlords-series

LOVED Warlords and would love to see them here. :/

Legends of Eisenwald will be similar to the HOMM style of games, but with more RPG, rather than strategy elements, but still strong in both departments.

Was this the one on Kickstarter, if so, I'm very interested in that game as well.

Played Warlords 3/4 quite some time ago, they were OK but IIRC there aren't many tactical options in battle. Its pretty much "pick a unit, see who wins". I prefer HoMM/AoW.