Alliance - Cenarius
Female - http://www.blogcdn.com/wow.joystiq.com/media/2007/09/ss23.jpg
Male - http://images.wikia.com/wowwiki/images/7/7e/Son_of_Cenarius.jpg
I think these would be perfect for the alliance and possible even a starting zone by or in the Teldrassil. I understand there would be problems with flight animation and getting on mounts. But Blizzard are very smart, they have overcome a lot of complications and i'm sure they could think of something creative. I also think it would be a good idea if they could have themselves as mounts just like the Worgen race.
Horde - Naga
Female - http://4.bp.blogspot.com/_0fk4iEPAmks/TAWYY0ilDlI/AAAAAAAAApM/qD1aIEBlOWw/s1600/Lady+Vespira+5.jpg
Male - http://casualhuntering.brigwyn.com/wp-content/uploads/2009/07/naga.jpg
I think this would be an interesting class to implement into the game. Of course, again there would be mount complications. I think it would be an idea of having legs on land but able to be in your true Naga form underwater. You could have a racial ability, like breathing underwater and swimming slightly faster.
I haven't really done that much reasearch but I wan't to hear what you guys think :) Can't you imagine it? A cenarius druid and a naga mage?
The naga hate everyone and everyone hates the naga. They've made enemies of themselves for decades and having some of them side with Illidan doesn't exactly help their case. They also can not survive long away from water.
I'd really like naga to become playable but I doubt it would work.
Humanoid races sound way better.. what about an Ogre? What about Pygmies xD.
Also the races need good reasons for joining the Horde and Alliance >.<