As you enter the Dreadnought, head north and talk to the Captain here. Show him the Pass and he'll let you go by as he takes his leave, but, if you tell him Wild Rose, well, you'll fight him. I do NOT suggest you fight him, although if your HP is about 1,000 or so and your Fire/Ice/Bolt is Level 7+, go for it, but BE CAREFUL. Either way, once you gain access to move on, do NOT talk to the Captains walking around, unless you want to fight them. They DO drop Golden Mails and Flame Bows, some REALLY good Equipment, but fight them at your own risk. Anyway, head east and go down the stairs and on this floor, you'll see a Treasure Chest being a locked door. Damn. But, wait, there's a secret entrance!
From the staircase, head east and go through up to the wall and you can go through it and once you do, grab the Treasure Chest to get the Crescent Sword. Though, you'll have to fight Sergeants and Warlocks for it, but they aren't that hard. Next, backtrack up the stairs and on the previous floor, head northwest and go up the stairs and head all the way west to find a Treasure Chest, which holds 400 Gil, then head back east and follow the path, ignoring the doors, since they lead to empty rooms and follow the path south, then east when you can and follow the path north to find a door. Enter it and in this area, head down the stairs and on this floor, follow the path and head west when you can and follow the path to find a Treasure Chest that holds a Shade Bow. Give it to Maria or whoever is using a Bow, if anyone, as it's much better than the Mythril Bow.
Next, head east and follow the path south when you can to find another Treasure Chest to the west that holds a Thief's Gloves. I suggest you give them to whoever uses a Bow in your party, if anyone, since they can't Equip a Shield, having their Agility boosted will give some some decent Evasion and higher Defence than the Mythril Gloves. If not, just give it to anyone you want. After this, head east and examine the locked door to free Cid and Hilda. Go in and talk to Hilda if you wish, as she tells you she's sorry to have troubled you and all, since they were coming to get you, but got captured. Then talk to Cid, as he tells you to destroy the Dreadnought with the Sunfire, as he and Hilda escape and they'll get out on his Airship. After this, follow the path back to the stairs, but this time, head east as far as you can go and grab the 2 Treasure Chests here to get 2 Potions.
After this, backtrack to the stairs and head up them, then enter the door and back on this floor, follow the path as far southwest as you can now and follow the path east afterwards and head down the stairs nearby. On this floor, just follow the path and enter the door and in this room, head down the stairs. On this floor, head east as far as you can go, passing the staircase in the middle of the room and on the other side you'll find 4 Treasure Chests. Open them to get a Titan's Helmet, Ice Shield, which you'll have to fight a Hill Gigas, Soldiers and Warlocks for, so, be prepared, Main Gauche and a Trident. Equip whoever you wish with any of these new pieces of Equipment, depending on how you're training and using your guys, especially since the Titan's Helmet and Ice Shield are better than the Mythril Equipment. Give, though, Gordon the Trident if no one else is using a Spear and use the Main Gauche if anyone is using a Knife weapon.
Next up, head west and go up that staircase you just passed and head up the stairs and on this floor, enter the door to the west and in this room, just head down the stairs. On this floor, you're in a maze now, with Captains blocking the path all around you. You CAN fight them, but they'll never disappear, so, be warned. To correctly get out of this hell hole, go north, then west, then south, then southeast and then east as far as you can and at the dead end, head north, then northeast, then west, then south when you can, then southeast and then follow the path around and enter the door. In this room, head north and examine the engine and use the Sunfire on it, as the Dreadnought begins to explode. Though, the Black Knight appears and tells you you haven't won just yet, as Maria thinks he's Leon, but Firion tells them they have to get out of here now, as they leave and you'll see them run from each floor of the Dreadnought.
After this, watch the mighty Dreadnought burn and explode into nothing, then, you'll see Cid take you in his Airship and drop you off at Altair. Go ahead and enter Altair and first, go ahead and sell anything you don't need, then buy anything you do need, heal yourself, then rest at the Inn and then make sure to remove all of Gordon's Equipment, plus rob him of his 2 Potions if you haven't already, as he's leaving in a minute. When you're ready, go and see the King. As you do, Gordon approaches him, as the King tells you his last words, which are making Gordon the new leader along side Hilda, having Mindu go and unseal the Ultima Scroll and for Firion to go to Deist and enlist the help of the Dragoons and the Wind Drakes. After telling you to take care of Hilda, he dies. After the heart breaking moment, you'll regain control of Firion.
So, go and talk to Gordon in Hilda always was and memorise "Dragoon", then ask him about it and he tells you about how the Dragoons can control and talk to the Wind Drakes. Memorise "Wind Drakes" and ask him about it and he tells you if you can find a Dragoon and a Wind Drake, they'll aide you and to get to Deist, go to Paloom and get on a boat. Well, looks like we're going to Paloom again. When you're ready, head on over to Paloom. At Paloom, you'll notice a new woman standing near the Sailor that'll take you to Poft. Talk to her and she sees you need to go to Deist and offers to take you there with her crew. Maria doesn't like this woman too much, but Firion takes her up on the offer and she tells him she'll be waiting outside of Paloom for him. So, leave Paloom and outside, head east and enter the Ship you see.