It seems that most of the Horde leaders play semi-major roles to say the least, but what about the Alliance?
King Magni does have a fairly significant role, though not much action is involved. I haven't seen anything out of Velen, Tyrande or the High Tinker. Velen really had the spotlight in The Burning Crusade though, so that's not much of a shocker.
There is a rumor that we're going to see Caverns of Time: War of the Shifting Sands following Fandral Staghelm around, but it's just a rumor. Don't get too excited over it, nothing concrete has been said by Blizzard or anything like that. It'd just a guess from some players.
My question concerns Cenarius. I read that the demigod is the son of Elune, who seems to be shaped like an elf in the pictures, and Malorne, who is, uhhhm, a deer.
Is that sort of thing... legal in Kalimdor?
Apparently so! Keep in mind that God-like deities do not really follow the same rules Humans do. Mild bestiality is not unusual in many polytheistic faiths and/or mythology. Note that I do not mean to imply that all polytheistic faiths are about banging dogs or whatever, that's not what I meant, so please don't get offended. A lot of the 'ancient' polytheistic faiths were this way, though.
One of the more well known examples is the Greek God Zeus seducing and getting it on with a lady while he was in the form of a swan. The lady involved was not his wife Hera, by the way. Oh, did I mention Hera was also his sister?
There's also the story of the Minotaur, in which King Minos was supposed to sacrifice a bull to the gods, but decided it keep it for himself. The gods weren't down with that and caused Minos's wife to fall in love with the bull. At her request, the architect Daedalus built a wooden bull so she could climb into it and let the animal make love to her. Thus was the Minotaur born.
Welcome to mythology. This stuff is completely normal here.
This may be to "Spoiler" to add here, but I would like to know some more about the Frostborn (those icy dwarves I think) and the storm giants and all that jazz in Storm Peaks.
The Storm Peaks is pretty much the number one place to go for Titan lore. Storm Peaks, the instances in that zone, and maybe a little Sholazar Basin. You learn a lot about the origins of the races here, what the Titans did, where they went, all of that. I'm not going to spoil everything, but the Frostborn seem to be an offshoot of the Earthen, and both the Frostborn and the Earthen come from the Iron Dwarves, the original Titan version of the Dwarves.
The Storm Giants were also Titan creations, and originally had a more metallic form. Other races, too.
You find out a whole lot more about why the races exist, why they've become what they are, and all of that throughout Northrend. I don't feel comfortable spoiling it all yet, because some of the reveals are really fun.