i did not level in stv until i was lvl 40 and if i had leveld in another area i probably could have skipped it altogether, only downside is the long travels you have to initially make to get a flight point in those non "mainstream" zones after you got that its the same as leveling in stv.
and as to difficulty, its actually easyer, less competition and less moronic 60s ganking.
i use this list
http://wowwiki.wikia.com/wiki/Zones_by_level_(original) to find apropriate leveling zones and just pick "the other one" when i see something like stv