Altea
After the king passes away and you learn Hiryuu and Dragoon from Gordon, you can leave to Palm. Talk to Layla and she’ll offer you a ship ride.
Get on the ship outside but she sends pirates after you. They’re easy kills, and you now have Layla as your guest 4th member and control of a ship!
You’re going to want new equipment for Layla and the Dist quest is coming up so be prepared. If you really have a lot of money to spend you may choose to go to Mysidia.
Mysidia
Attempting to go here this early is a real risk – the battles on water (though the encounter rate seems rare in some areas) can be difficult specifically the SeaSnakes.
To get here is complicated too. Only attempt it once you have enough money to make it worthwhile. Begin at Altea and sail south and along the north coast going east. You’ll eventually see it split so take the south path that wraps around west. Keep following the land here (now on the south coast going west and eventually south). A desert should be west and north of you as you’re going along here. Eventually you’ll go north if you follow the land and when you reach a river to canoe…ignore it and save.
You are going to run east of where this river starts and that’s about where Mysidia is. The problem is the random encounter or two you’ll likely face as you run east. Hopefully it’s a Bomb and Grenades or a Brain, because the other enemies can kill you very fast. That’s why you save, and if you die then just load up until you get a favorable random encounter.
Inside Mysidia is a huge collection of magic, including Holy, Change and Wall. For weapons, you should get some Ice Bows for the lady’s and Ogre Axe for your axe wielder (likely Guy). The Armor Shop has some goodies as well, like Knight Armor for everyone and Thief / Giant Gauntlet’s and Giant Helmet’s. As stated above, it’s really only worth it if you can come here with a lot of money and buy lots of it. With this new stuff the enemies around here are at least doable, and once you get back on your ship and start going back east and north you’ll see the sea enemies are much easier as well.
Dist
Another place that is a treat to sail to. It is in the northeast corner of the map but it’s hard as hell to find an opening to get over there. You could sail all the way to the west (west of Mysidia) to get there.
A boy is inside. He runs when you talk to him, then you see him again and he does the same thing. In the next room, take a left for a Cottage and east for the boy and his mom. Talk to them about Hiryuu’s and Dragoon’s. They are the survivor’s as their husband / dad died as a dragoon. Go to the southwest here for stairs and FenixDn. Go to the northeast stairs in that previous room.
Here, go west for 8 treasures – Winged Sword, Heart, Elder IQ, Needle, Eyedrop, Antidote, Crucifix, and EchScn. Now go south and take the second door for Stone Magic, Curse Magic, and Stop Magic. You can go back and visit the sick Hiryuu if you want.
Dist Cave
North of Dist is the Dist Cave. Go east as you enter for 30 Gil and go east as you enter. A Dragoon Corpse is ahead of you and if you search you get the Pendant.
Back to the initial intersection and take the southeast staircase. Go northeast then work your west west and north for Mithril Armor and south for Mithril Helmet. Southwest for a Magic Staff and southwest more for a staircase. East of here for a Mithril Shield.
Back to the beginning and take the southwest stairs. East for a Potion