Skining, Leatherworking and the Tauren

If you are a starting a Tauren, I highly recommend picking up skinning and leatherworking, at least at first, even though there's that "Cultivation" herbalism bonus.

Here's why:

Taurens get a choice of four classes, three of which wear leather, one mail
Orcs get five classes, 3 leather, 1 cloth (warlock), and one mail
Trolls 6 classes, 3 leather, 2 cloth, 1 mail,
Undead 5 classes: 1 leather, 1 mail and 3 cloth
Bloodelf, 6 classes: 1 mail, 2 leather, 3 cloth

Human: 6 classes, 2 mail, 1 leather, 3 cloth
Dwarf: 5 classes, 2 mail, 2 leather, 1 cloth
Night Elf: 5 classes, 1 mail, 3 leather, 1 cloth
Gnome 4 classes, 1 mail, 1 leather, 2 cloth
Draenei: 6 classes, 2 mail, 2 leather, 2 cloth

I haven't actually done much with the Draenei, so I'll leave them out.

So of all the possible combinations, Taurens have the highest percentage of leatherwearers. So it makes sense in terms of a world story line that there would be some incentives for Taurens to pick up skinning and leathercrafting.

Next consider the fact that the skinning and leatherworking trainers are right there in the very first place you come to as you leave the baby area — Bloodhoof Village. There's also a cooking trainer, but no herbalism trainer until you get to Thunder Bluff. Everyone else, expect Night Elves and Humans, has to travel to the main city to visit the skinning and leather trainers for the first time.

Many of the early quests for the Tauren involve killing animals. If you pick up skinning and leatherworking at level 5-6, you'll be making your own armor and armor kits almost immediately. Plus you'll have several stacks to put on the AH when you get to Thunder Bluff during your questing, rather than making a special trip.

And once in Thunder Bluff, run upstairs to the middle rise to pick up and turn in a skinning quest and a leatherworking quest. The leatherworking quest reward is a pattern for a 6 slot Kodo Skin bag. Wow. Bags at low levels make life so much easier. Even tailors can't make bags at this early. Kill kodos while running around Mulgore, make your own bags, then sell them when you can afford bigger bags. OR don't read the recipe. Instead buy your bags off the AH (3-5s for 6 slots), and keep the recipe in the bank. When you get to Booty Bay in the mid-20s for the Warsong supplies in Ashenvale, put the Kodo skin bag recipe on the neutral AH. This is a horde only recipe and it's a quest reward. You should be able to sell it for several gold.

Once you've done the recipe thing, you can drop leatherworking if you choose and switch to herbalism. With a +15 bonus, you won't lose much and should hit The Barrens at 50 or so, enough to gather mageroyal.

Other races:
Dwarves (or Dwarfs) also kill a lot of animals in Dun Morogh and Loch Moden. So skinning is a good choice for them, too. Humans get a lot of cooking quests in Westfall. Night Elves have a Skinning trainer along the road to the main city, but since they aren't killing as many skinnable beasts, they reach Darkshore with a lower level skinning, unless they want to spend some time grinding.

Any class and race will be fine. It's just there are these bonuses with Taurens. A couple of quests, a horde only recipe to use or sell, and the option to switch to herbalism and not lose much. If you do switch to herbalism, be sure to visit the herbalism trainer in Orgrimmar when you're there on other business to pick up an herb bag. None for sale in Thunder Bluff.