Since Shattrath "downtown" will already cover the major faction cities, I'd offer taxi service to:

a) places that are a pain to get to, and/or
b) places most people need to go while levelling up.

What comes to my mind is:
- Kargath (dunno for alliance, but for horde it's a marathon. Quite a few folks do quests in BRD still)
- [s]Stonard or[/s] BC portal, respectively. [Edit: Thanks for the hint. Happens when you never play a mage...]
- Winterspring? (far, but not enough demand I suppose)
- Gadgetzan (*thumbs up*)

Cheers