The MSQ that leads you to the other cities is at level 15. You just need to progress them.

The quest "The Gridanian Envoy" will lead you to Ul'dah and after that, the quest "Call of the Sea (Gridania)" will lead you to Limsa Lominsa. These quests unlock the airship you need to first travel to the other cities, unless you decide walk the entire way. Once you reach the other cities, you can unlock the aetheryte in each city so that you can teleport to them easily.