This is strictly my own personal preferances, but I strictly play horde and I have an undead lock, orc warrior, troll shaman, tauren druid, and blood elf paladin. I also have 3 goblins and 2 other blood elves, but I mention the first few simply because I've chosen the races that I feel best fit the classes. Undead have a very dark feel to them that is supported by the lore, just as the orc are (for the most part) a very brutal and savage race, which I feel fits a warrior best. The tauren are obviously very in tune with nature and animalistic in look alone. Blood elves have a very rich background as blood elves from the original high elves. Read up on the lore of what you want and go with what feels right.