You will need to go to the Castle of Ordeal to pass BAHAMUT's test and prove your courage. There are three ways to approach the Castle. The first is to land your AIRSHIP at the western tip of the peninsula to the north. From there you will need to trek far to the east, then back west until you reach the Castle of Ordeal. This path requires the most walking, but the encounters on this route aren't terribly dangerous. A number of the creatures you'll fight are new, but don't demand any special tactics. Saber Ts have an extremely high critical hit rate of 35%, and the CATMEN that often accompany them are Poisonous. SAURIAS are an interesting foe that can inflict Stone, while WYRMS take some effort to kill but don't present a notable threat. You may run into Sand Ws during the middle part of your trip, and their CRACK ability can be deadly if you're not lucky. ARUB will protect you from its effects.
There is a shorter overworld path, if you're willing to risk some more dangerous battles. If you fly east from the Castle of Ordeal, you'll find a grassy area southeast of a small desert. You can land here and then travel west (making sure to go through the desert and not around it), and cut your trip time by about 1/3. The danger is that the first leg of this trip has Mirage Tower area encounters, which are the most dangerous on the World Map. The ANKYLOS and R.ANKYLOS here deal incredible damage, don't go down easily, and don't drop much in the way of Gold. TYROS and WYVERNS aren't too bad, but you definitely don't want to run into a pair of Sand Ws. Fortunately, they are quite rare, as is the monstrous T REX.
If you want to circumvent World Map encounters entirely, the third option takes longer but is easily the safest of the three. Fly your AIRSHIP back to wherever you last docked your SHIP, and sail to the north continent. (If your SHIP is in the vicinity of Crescent Lake, this is most easily achieved by sailing south and allowing the map to wrap around.) You may have noticed a short river in the vicinity of the Castle of Ordeal. You can dock the ship here by using the CANOE, and then you will have only a short walk to your destination. The only downside to this route is that you will likely fight a lot of trivial Ocean encounters, which are just boring at this point in the game.