Eredar are a class of creature imbued with magical power and higher ranking eredar have more magicla might backing them up.
Worgen are basically humans who got cursed with a bloodthirsty feral side. Genn was a king by blood with no other real traits beyond his ability to lead. How is he all that different from other worgen? well he's got a name. Sure. But as far as skills go he's basically just stated that he's got the worgen thing going on.
edit:
forgot Genn's passive traits of lack of foresight and hotheadedness. Negatives on sense motive skill ranks and bonus for leaping to conclusions.
edit2:
and yes. the undercity existed prior to the formation of teh forsaken, apparently. It was a crypt/prison and Orggrim Doomhammer was apaprently stuck in there for a time. Arthas took it over with the scourge and well later the Forsaken took up residence and dubbed it the Undercity. I doubt many casters took teh time to learn the layout of the royal crypt or a prison though.