For me, it's the actual complexity in the "metagame."
The sheer amount of decisions that need to be made, the uniqueness of any given turn, the situations that emerge as a result of all these individual mechanics -- these are the gameplay elements that make it such an entertaining and addictive experience.
The scale and micromanagement of HoMM (at least the older titles) is largely avoided these days as it's difficult to balance and represents an immense learning curve, but I think it can be well worth the price of entry.
I download HoMM II from GoG a while ago, and decided to write a brief overview of the game and expound a bit more on the above point in my blog. It's a topic that I could go on about for a long time, especially if I were to catalogue all of my experiences, but I figured it'd be interesting to ask everyone else for their opinions.
So, why do you guys (and gals) like these games so much? Any particular moments you recall fondly that -- for you -- capture the quintessence of the game?

The HoMM 2 atmosphere did it for me. The visuals, music, sounds, little tiny animations of all the things in the world, etc. all add to a wonderfully immersive experience. The whole game felt very much alive.

your blogpost pretty much sums it up

Definitely a combination of metagame and atmosphere. HoMM2 especially appealed to me with the vibrant colors and music (I have yet to find another game with opera, but I love it). Also, the vampires go "bleh!" when they attack ;)
But really, I get immersed with the desire to find new resources, artifacts, and to build my army in unique ways, just to see it get tested against random mobs and opponents alike. Whether I wish to be efficient with resources, fast in completing the map, or any other desire, I have those options.
Truly great.

Heh, yes, the vampires going "bleh" as they did what appeared to be a weak backhand always amused me.
The amalgamation of various mythologies was cool but somewhat generic, yet the colourful presentation made it all look interesting. What kept me coming back, though, was the knowledge that every scenario would play out quite differently thanks to the sheer variety of game elements.

Yep, metagame and atmosphere.
The overall atmosphere (music, graphisms, methologies/creatures) is what make Heroes special, the metagame is what make you return to the game again and again.

I'd like to add that HoMM tends to please girls. My mother (50 something) loves HoMM since the 2. That's one of the 3 computer games not online she ever played (lemmings back then, and the HoMM and Civilization serie).
My girlfriend ALSO likes HoMM. With Civilization (yet again), it is the only non-adventure game she ever plays.
My girlfriend considers it a calm and relaxing game, with a great charisma and atmospher.

Give me your girlfriend!
=)

nono, you don't want that. before you know it, she hogs the computer and you're like reversed in your 'roles'
you: "honey, i'm going to sleep, won't you come with me?"
she: "no DAMN STUPID NECROMANCERS"
believe me, it ain't pretty.

I've got another 'type' at home but I -totally- see what you mean... =D
Ha, those girls!
Edit: What the hell with reply notifications on GOG? Leave (Britney) me alone!

i didnt found any thread like "yesterday i had a blast..." :)
So i will write it here.
I like homm3 because it always gives something unexpected.
Yesterday i choosed to play inferno town, because i was mostly playing tower castle stronghold often, and also because i wanted to listen inferno town music. :)
The game went brilliant, in the first week i found armageddon scroll.(thats the first time i find this spells' scroll. :) ) Wreaked havoc using it and 10efreeti.I even managed to win dragon utopia with 9of efreeti.Seriously, this game gave so much fun.All towns rock! :)
P.S. the inferno town itself looks magnificient.Golden sun setting far away, and demons arising :)
p.s.s. sorry for bad english

Only with the Grail... =)
But I agree that sun setting with the grail is beautiful. I love this town... *_*
By the way, Castle and Barbare Grails aren't so lovely. A viking in gold? A... pike? =S. Much prefer Rampart/Fortress/Tower (and Hades) ones.

But the Inferno grail's special effect is next to useless, IMO :-/
I mean every week is the week of the imp/familiar? Seriously?

=D. Well... ok that s*cks. But it's nice looking!
Edit: Replies notification SNAFU. =)

I'm not realy into turn-based games (to be honest - I hate them) but this one is just marvelous. I loved music and atmosphere. Yes, that one of a kind atmosphere!
I just bought It on gog - I only had a version with no expansions, so i'll probably stay with my PC all night :)