Two Players, Two Differnt Starting Towns

[Naberrie]

He said it's not impossible.

Also, even if you were in the same city, you would end up soloing some things anyway. Many of the early class and storyline fights are instanced, meaning they are solo only, and you wouldn't be able to help each other. It's not until you can travel freely between cities at 15 that you begin doing group instances in the form of dungeons and primal fights. So by the time you need to group together you'll be able to meet up quite easily.

[Niwashi]

You can travel by foot between Ul'dah and Gridania. You need to go to Ul'dah > Central Thanalan > Eastern Thanalan > South Shroud > Central Shroud > Gridania. I wouldn't recommend it unless you are about level 20-25. But by then you will have an airship pass through the main story quests. You could always see if you could get a high level character to escort you.

It can be done fairly easily at any level. You don't need to be leveled enough for the mobs along the path so long as you don't fight them. You just need to be able to recognize the icons indicating which mobs will aggro and which won't. There aren't that many aggroing mobs along the main path, so it's easy enough to give the few there are a wide berth and simply avoid any fights. I actually did it accidentally while I was just out exploring at around level 12 or so.

Of course, that still leaves the issue that once a pre-level-15 character gets to the other city, it's not where their main storyline quests are. The first 15 levels of main story quests are all in the city you started in. You can't do the ones from the other cities. All you'd have is side-quests.