FIRE POWERED SHIP
My Level: 26
The Fire Powered Ship is at the dock south of Karnak. Make everyone Red Mages with the Learning ability for now, so that we can grab a couple of Blue spells along the way. We'll be Red Mages for a good while during the actual quests, it helps a lot in getting all those 999 points for the Red Mage's final class level. Plus it is the best class at the moment for this portion of the game.
Cid is at the ship deck and opens the door for you. Head inside. This place can be tough considering we are still early into the game. Follow the paths down the stairs. In the first mechanical looking area go through the door north of you on the bottom floor. It leads to a Mithril Glove. Go upstairs to the upper path and then down again to the chest in the upper left corner and it has a Cottage. Take the stairs on the left side of the room that go up. Follow the path to get to a chest with an Elixir, now go back down. This time go down the stairs on the right side, there is a chest with another Elixir down there. Go back up and head through the north center door. Flip the red switch to use the elevator. Open the chest with a Phoenix Down in the next area. Use the next elevator.
You'll see a chest south of you, but there is a conveyor belt pushing you back in the opposite direction. Go through the ducts and use the elevator at the end of the path. A conveyor belt puzzle.... The leftmost path leads to the area you just came from. The third path from the left leads to that chest you couldn't get to earlier, open it for a Thief Glove and ride the conveyor belt back to the ducts and make your way back to the conveyor puzzle. Take the rightmost path and then go through the duct to your right, follow it and you will see a chest with a Green Beret. Ride the conveyor belt east and go through the door to be back at the puzzle, take the second path from the left. From where you ended up take the stairs to your left, flip the switch, and go north for a chest with a Moonring Blade. Now go back and enter the door left of you. Do not take the conveyor belt in here, it takes you back up to the puzzle again. Go through the door to the left. Save at the save point. Now you can either take a moment to get the two new Blue spells here, or go fight the boss. Wait, no there is a switch puzzle first.
Just a little bit more to go. In this puzzle with the switches it seems a lot worse than it actually is. Flip the switch third from the left, then the second switch from the left, then the leftmost switch, then the rightmost switch, then go south and flip that lower of the two switches there, then go back up and flip the second switch from the right, then go south again and flip the upper of those two switches. Grab the Elixir from the chest and exit through the door. NOW it's boss time. If you still have not learned the Blue spells from here and want to, now's your chance.