On one of my characters, the guy in the wagon at Whiterun will take me to almost any city in Skyrim.
On my slightly newer character, he only lets me go to four cities - Markarth, Riften, Solitude and Windhelm.
My first character has all those plus places like Morthal, Winterhold, and Falkreath.
What's the reason behind this? It's not based on which cities I've visited (as I've only visited Riften out of the four on my second character).