As you enter the Ship, it starts to sail a bit and after a little while, a scene takes place, as it seems Leila tricked you! Apparently, she's a Pirate and she wants your valuables in return for your lives. Though, you aren't going down that easy, so she summons her men to fight you. This is NOT a hard Battle. If you've played Final Fantasy I, this Battle should seem familiar to you. After the Battle, Leila surrenders herself to you and she's surprised Firion wants her to join them. After this, she'll join you AND give you her Ship! Yay, your first vehicle. So, next, onward to Deist, home of the Dragoons. Pull up your Map and you nee the island farthest to the northeast with the yellow and pink dot on it? That's Deist.
Also, Equip Leila if you wish, since she'll be with you for a good while, but don't really train her too much. Do give her the Main Gouche you have, since she's good with Knives and a Shield instead of a Sword in her other hand and don't forget she's Left Handed, so Equip the Main Gouche in her Left Hand and the Shield in her Right Hand/ (Also, give her Gold Hairpin to one of your other party members and give her what they were wearing.) Anyway, head to Deist and once there, enter Castle Deist.
As you enter this place, notice how there's no Monsters here, which is a good thing. Then, head north to find a boy and talk to him, as he runs off. Then, talk to him again and afterwards, follow him up the stairs. In this area, grab the Treasure Chest to the west to get a Cottage, then head southwest and go down the stairs here and back on this floor, grab the Treasure Chest here to get a Phoenix Down. Next, head back up the stairs and back on this floor, head to the northeast and head down the stairs here and back on this floor, head west and enter the door here. In this room, open the 8 Treasure Chests here to get a Gold Needle, Sage's Wisdom, Saint's Spirit, Wing Blade, Mallet, Cross, Antidote and an Eye Drops.
I suggest you Equip Firion or whoever's your Swordsman in the group with the Wing Blade, as it's a GREAT weapon. After this, exit the room and head back east and then go south and enter the second door here and in this room, open the 3 Treasure Chests to get a Curse Scroll, Stun Scroll and a Stop Scroll. None of them are that good, so don't bother with them unless you wish to, but you won't need them: EVER. After this, exit the room and head to the southwest and grab the Treasure Chest here to get a Unicorn Horn, then head back northeast and go up the stairs. Back on this floor, talk to the kid's mother here and she tells you about the Wind Drake in the room behind her, as well as about her husband who disappeared. Though, the Wind Drake can't be understood unless you have the Pendant and she tells you about how she thinks it's in a cavern north of here and it's only a couple levels down.
Anyway, ask her about the Dragoons if you wish, then go ahead and leave Castle Deist and outside, head north now and enter the cave you see.
As you enter this place, don't expect to be here long, since you're just going to get the Pendant and then get out of here. Don't worry, you'll get to fully explore this place in… oh, 5-15 minutes? Anyway, once inside, head east and open the Treasure Chest here to get 30 Gil, then head northeast and follow the path down the stairs here. On this floor, examine the Dragoon's Corpse nearby to find the Pendant. Once you get this, head back to Castle Deist and once there, head back to where the mother and son are and enter the door near them. Inside, you'll find the Wind Drake, so, talk to him to learn about how he'd dying, thus he can't join you. Ask him about the "Wind Drake" and he'll give you the Dragon Egg and ask you to put it in the spring in the Deist Cavern.
Talk to him again to see him "die". Which is funny, since if you continue to talk to him, he keeps dying. Anyway, head back to the Deist Cavern now and once there, head southwest and go down the stairs here. On this floor, follow the path and get the Treasure Chest you see to obtain a Potion, then head down the stairs nearby. On this floor, just head down the stairs to the northeast and on the next floor, just head northwest and down the stairs. (Also, if you can, fight Hill Gigases here, as they drop Titan's Helmets and Titan's Gloves, two GREAT pieces of Equipment. Definitely worth the time to get.) On the next floor, follow the path and grab the 4 Treasure Chests you come across to get a Knight's Armour, which is guarded by some Adamantoises, Saint's Spirit, Sage's Wisdom and a Flame Bow.
I suggest you give Firion the Knight's Armour or whoever has the lowest Defence rating and to give Maria or whoever is your Bow person, if you have one, the Flame Bow, if you don't have it already. Once you get all of this, backtrack to the starting floor of this place and if you need to, leave now and head back to a town to heal up. If and when you're ready, head down the stairs to the southeast and on this floor, follow the path and head south when you can and grab the Treasure Chest here to get a Mythril Helmet. Then, head back north and grab the next Treasure Chest you see to get a Mythril Mail, then continue to the west to find another Treasure Chest, which holds a Mage's Staff, but it's guarded by Screamers.
After this, head back east and go down the stairs here and on this floor, ignore the bridge, as in, do NOT go across it. Instead, head north and grab the Treasure Chest you see to get a Mythril Gloves, then continue on and get the next Treasure Chest, which holds a Mythril Mirror. After this, head back up the stairs you entered this area in and now head west back on this floor and head down the stairs you see. On this floor, you'll be on the other side of that bridge now, so, grab the Treasure Chest nearby to get a Mythril Shield, then head north and follow the path around and head down the stairs you see. On this floor, follow the path around and grab the Treasure Chest here to get an Acid Bottle, then head down the stairs to the south.
On this floor, follow the path to find 4 doors, which the door second to the right is the correct one. Once you go through it, get ready for a Boss Battle. If you need a strategy, head to Section VII. Boss Guide now, otherwise, fight this yourself and move on. After the Battle, go over to the Sacred Spring and use the Dragon Egg on it and afterwards, go ahead and Warp out of this place. Outside, head back to Castle Deist if you wish, just to see that the Wind Drake's gone now, but you don't have to do this. Either way, head back to Altair and once there, enter it.