Martian12: I've never played a HoMM game before. Do they have an interesting plot or the story is conventional? I always believed that these games rely on their gameplay alone and the story is rather "decorative". Also, do the series have an overarching story or each game is a standalone experience?
The overarching story started back in 1986, with first (RPG) games being playfully crazy, mixing fantasy-like settings with sci-fi advanced civilizations and usually done by the Van Caneghems couple. The series never fully consolidated from this toward some "really serious" setting, keeping some pun references here and there, stealing from other mythologies, feeling sometimes even naive and silly [if you are used to the Tolkien's attention to detail and building up the whole Hobit thing down to the smallest detail].
That said, each game is sort of self-contained, having it's own particular world, and the games are interconnected usually very vaguely, every now and then completely changing involved worlds/galaxies, enemies and guardians, where only the core premise of clash between "Ancients", "Kreegans" and their various creations going-not-as-planned is connecting them. That, and lot of cameos, reusing character names, creatures, world names, etc..
The Heroes games lack the sci-fi portion of stories, and focus on the worlds already descended into barbarian medieval-like state, usually predating the RPG game epoch, telling particular stories of rulers of that world. In RPG games you usually scratch that on surface by finding some historical references of those rulers, or ruins of their world.
I think the story in M&M games is a bit more toward "decorative", it's often fun, sometimes breaking immersion by crazy things, like one RPG contains map of the New World Computing office, etc.. It wouldn't probably stand on its own without the game, but more than good enough for game.