Travel between those two cities isn't impossible on foot, but there are class quests every 5 levels to deal with, and the main story quest lines are based around the starting city and different for each character. If you did meet up, the traveler would have to go back and catch up with all those quests anyway, before they could get an airship pass, enter dungeons, etc.

Tank + healer is a good combo. Form a 2-person party before registering for Duty Finder (behests Lv10+, dungeons Lv15+) and your waiting times could be on the order of seconds rather than much longer.