Tower of Zot
In the room where you regain control of your party, go to the north-west and follow the corridor to the top. The chest there contains Fire armor. Head to the north-east corner and go through the door you find there.
On the second floor simply go south as far as you can, and when you reach the southern edge, head west. Then go up to find the door. The chest that's visible a bit to the east contains a FlameDog and a Fire Sword.
To return to Toroia, head back to the starting location in the bottom-left corner of the first floor. While you can explore the world using the Black Chocobo, the airship will only be a route between the city and the tower.
In this room, take the bottom path and go as far to the east as possible. Then you will head north, and then west again, and you will come the next door. In this room, you will head to the south, and then as far east as possible. Now head north and go through the door.
On the fourth floor, you can opt to go directly to the right, or visit the rooms to the north for some items. The left door contains a poison claw and a fire shield. The middle door contains an earth wrench, and the right door contains a wizard robe.
Save Point and Magus Sisters
The first door is a save point. After saving, go toward the next door. You will be interrupted by the Magus Sisters and a boss fight will begin.
The key to defeating this trio is to target the one in the middle sister, Cindy, who can heal and revive the others. Her sisters will protect her by casting Wall on her, but they are all weak enough that it does not really matter. The trick here is to not cast reflectable spells on Cindy. Don't bother casting Wall on your characters, as it will just waste a turn. The sisters are very easy to defeat with normal attacks. Make Tellah cast Berserk on Cecil and Yang and then target one of the other sisters with direct damage spells. Have Cid repeatedly use his hammer to cast Quake and the sisters will be killed in no time.
If you slay the front or back sisters (Sandy or Mindy) first, Cindy may revive them in a single move.
Tellah Fights Golbez
You should return to the save point because you will have to fight in the next room. Unequip any desired items from Tellah, and proceed to the final room. First, a cut scene will begin in which Tellah fights Golbez. Tellah dies because of the battle. Go speak to Kain and he will join you as does Rosa when you save her.
Equip Rosa with the best items, and try to leave the room, but before you can leave, Valvalis will fight you.
Barbariccia (Valvalis on SNES)
When she starts to spin around you must have Kain jump to stop the spinning, weakening both her attack and defenses. Otherwise, just have the rest of your party attack, and have Rosa heal.
Once you defeat her Rosa will warp you back to your room in Baron. Kain will give you the Magma key so that you can reach the underground.
Exit Baron castle and the airship will be outside. Get in and fly directly south of Baron. You will come upon an island with a cluster of mountains and the town of Agart. Go into the town and walk to the well in the middle of the town. When you approach the well, choose the Magma key and it will fall in, opening up the underground. Fly in with the airship.
When you fly into the Underground, a cut scene will begin and you will be attacked by the Red Wings. Once it is over you will be right next to the Dwarf Castle. Unequip Cid, as he will be leaving your party soon. Keep going straight ahead until you reach the throne room. Speak with the king, Cid will leave your party and you will see dolls bouncing in the background. The king will have you check it out.
Calcabrina (CalBrena on SNES)
If you are able to kill all of the little dolls quick enough, the battle will be simple. Otherwise you will have to fight the large Calcabrina. Be sure to fight this quickly, because otherwise, she will split apart again and you will start the cycle over again. After defeating the dolls you will be led directly into another battle.
Golbez will attack you to the point of near death, but Rydia will come in and save you. Quickly revive one of your party, and have Rydia use a call magic (Titan is pretty effective). Golbez will be defeated fairly quickly if you survive long enough. If Kain is airborne (from Jumping) when Golbez uses Hold Gas, he won't be affected or killed with Rosa and Yang, which lets you fight with three people instead of just Cecil and Rydia. Once you defeat him, the king will open up the underground passage for you to go after the next crystal.
Note: If you cast Warp in the Throne room, you will return to the secret crystal room where you can collect the Dark Crystal. This crystal identical to the crystal found in the Sealed Cave, and allows you to skip past that entire area.