Yeah, you aren't allowed in any towns. You can however, visit the lab where you get Bahamut and fight the Ultima Weapon, and the tower where you got Odin. You have to exit the world on one door, and then find the other doors to make them accessible. You'll have to get a chocobo, and then walk across the world in the shallow water to your airship. That makes everything a LOT easier.