Mmmmmm, HERO
Many others have already made points, so I'll try not to repeat too much. }

I only started playing HERO in the Big Blue Book-era (BBB, the 4th edition) so my experience is more recent and less about the early days not-so-goodness, but that having been said the 5th ed (Fifth Rules Editition, or FREd) as a book is excellent -- still a bit dry and the layout's not fancy but there are about a tonne or two of examples of how to build things, and the index is a standard that all game companies should aspire to. And the supplements are fantastic, with a whole tonne of advice, examples, pre-made things, etc. HERO support is also something that many companies should aspire to -- the number of super-think books HERO has put out in a few years is astounding.
No surprise, I too count HERO's flexibility as its greatest point. No need to multiclass wierdly (no classes at all, hooray!), or devise a PrC (humourously added to DnD to get around the limiations of classes), or etc -- you want to do something, so long as the GM approves it, you can do it. A light fighter? No problem. A person who has only a few utility spells, mostly fights with big weapons? Go for it.
WRT HERO being complex, or, more specifically, math complex: not really. Addition/Subtraction/Multiplication/Division is all you need to know. The first two are already required in all other games, the last two can easily be done with a calculator if one isn't keen on using the provided tables and/or on paper. And all those need only be done during character creation. During game play, the math isn't more difficult than any other game (+/- only). True, there may be more to keep track of, but most of the 'detail' are optional rules, and there are plenty of other optional rules to simplify as well. How much you want to have depends on your style of play.
Two things that may give new players pause is this: one, understanding the idea of an effects-based system (ie, you pick the effect you want, then define how that happens/what it looks like, rather than picking an ice-bolt spell or a fist-of-doom feat), and just the fact that you really CAN do anything -- too much choice is like the blank page. It can lead one to sit and stare blankly, with no starting point. }
HERO really was made for Champions; there are certain things that need to be tweaked to make it work in different genres. Of course, one should pick up the various genre books if they'll run a game in that genre, and that provides a lot of help. While it is commendable to try to keep point costs the same accross all genres, I think they could've done a good deed by providing an option to change certain costs to help mold the rules into each genre.
Is HERO a rules-"optimizer"'s dream? Yep. Been there, done that. }

Is it worse than DnD? Maybe -- but check out the power gamer/smackdown/etc forums/threads for DnD and you'll see that it isn't impossible to break the system as well. In many ways, it can be harder to catch in DnD since everything is in separate books and are all 'special conditions', ie, feats and classes and rules that due to the nature of class-based system are independant. The designers can't really check to make sure that combining A with B won't make A*B isntead of A+B in terms of effectiveness. With HERO, all the special thigns are in the main book. That isn't to say there are not broken combinations, even in the basic stats (*cough*strength*cough*), or that the GM needn't stay on their toes, but its not necessarily worse than DnD. And for those who say Core Only! in DnD can as easily say No Frameworks! or Max 1.5 Limitations! in HERO. }
Also, in some ways, one might find powers more balanced in a more limited Fantasy Hero setting than the unbridled champions.
The Fantasy Phonebook (aka the Fantasy Hero supplement) is an amazing tome of options, and is great for almost any system on its info alone.

For HERO, there are 13 or so magic systems as examples (and the Fantasy Grimoire book has 5 billion spells), shows how to emulate many feats from d20 in HERO terms, and provides 'look out for's and 'if you change this, this could be the result' and 'if the campaign tone is this, then this is good'. Its actually MORE pages than the main rulebook. Its scary and cool at the same time }
Also, one thing to remember (because some seem to make this assumption) is that just because you CAN stat everything out in HERO, doesn't mean you HAVE to. Yes, handcuffs are 2d6 Entangle, Def 3, Persistant, OIF Breakable, etc, etc -- unless it's important (your characters are trying to break out of them) they're just handcuffs, they just work -- its the same as any other system. A door is a door until you need to know if you can chop through it.
This is getting longer than I expected it to.
The short of it:
Is HERO flawless? No. But then, few other systems are.
Does HERO have a big learning curve? Maybe -- lots of options, but they are options, and char creation can be fine if you have a good grasp of calculator.
What does HERO provide that d20 or others may not? The easiest route to limitless character concepts and flexibility. A set of coherent rules that are linked and thus have the potential to be more inherrently balanced than individual-cases tacked onto the core system, be it for weapons, special attacks or magic.
Does HERO make more work for the GM? Debatable. Certainly, if not using a pre-packaged campaign, there may be more work at the start to set up all the limitations and etc, but the genre books help tremendously in this regard. Making up enemies and NPCs may be tougher -- but at the same time unless you really care about the point cost, not by much. You should have a general idea based on the NPC's attacks/defences how strong they are. Does it matter if they cost 5 points or 50? What matters is if it does 5d6RKA AP Penetrating AF5 AE Radius or if it does 3d6N.
Like all systems that claim to be 'Generic' or 'Universal', HERO actually works best as written under certain types of games (and thus isn't really universal). But with the options provided in the Genre books it can still work extrordinarily well in many campaigns, and the benifits of flexibility can shine through.
Kannik