After going through the Underground City and getting rid of the Scorpion Gang, you can enter the Grand Palace.
Grand Palace 1F
On the first floor, there are Heck Hounds, Turtlances, Gremlins, and a Doom Sword. Go through the door in the back wall of the lower floor.
There are three Gremlins floating above the water in here. Go into the room on the left and use Gem Missile on the orb. Go back to the last room and go into the room on the right. Use Freeze on the orb in the room on the right. Go back to the first room of the palace, go upstairs, and go up the stairs in the middle of the back wall.
Grand Palace 2F
Go south from the stairs and use the whip to reach the small platform to the south. From there, Use the whip on the pole to the left. Go through the door north of where you end up. Use Air Blast on the crystal orb in the north part of the room, then leave this room.
Keep going south to go through a door in the south wall. Go to the far right side of the room and go through the north door. Continue north and go through the door into another crystal orb room. Use Fireball on this orb, then leave the room.
Keep going south to go back through the door that you came through. Go to the middle of this area and go up the stairs in the north wall.
Grand Palace 3F
There is a door blocked by bars in front of you. Go east, then go through the door in the south wall (to the left of the green torch). There is a chest in this room. Be sure to get it, because there is a bug that might make it disappear if you leave and come back without getting it. It contains a Sword's Orb.
After you get the Sword's Orb, go to the far east side of this room and go through the door there. This is another crystal orb room. Use Dark Force on this orb, then leave the room.
Now go to the far left side of the room where you got the Sword's Orb. Go through the door there and use Lucent Beam on the orb. Leave the room.
You're back in the room where you got the Sword's Orb. Go east and through the door that is just to the right of the door to the crystal orb room. You will be back in the room with the bars over the door. Use the bow or other long-range weapon to hit the wall switch to the left of the bars. You could alternatively go up the stairs to the right of the bars and go around the path until you get to the wall switch, but this is much quicker. Go through the door that the bars were blocking and continue north up the stairs in the back wall.
Go to the northwest corner of the room and go down the stairs. Follow the path around until you reach some stairs near the top middle of the room. Go up the stairs.
Grand Palace 4F
Go to the northwest and northeast corners of the room and step on the switches there to reveal stairs to the south of each switch. Go down each set of stairs and step on the switch near each one. This opens the path to the south. Go to the southwest corner of the room using the whip to get across. Go through the door there. Use Lunar Magic on the crystal orb in this room, then leave. Go to the southeast corner of the room this time, using the whip to get there. Go up the stairs in the southeast corner of the room.
Grand Palace 5F
Step on the green button and you will be faced with the boss.
Snap Dragon
Use Exploder on Snap Dragon. It only has 1215 HP, so it should be a quick battle. You get a Javelin's Orb afterward.
Go to the southwest corner of the room and go upstairs. You find the Emperor on the altar... dead. Go behind the altar and through the door. You learn that Fanha killed the Emperor and is Thanatos's follower now. Thanatos plans to take over Dyluck's body to become young again. Fanha transforms into Hexas and attacks you.
Hexas
Use Earth Slide or Thunderbolt on Hexas. She can use Pygmus Glare on you, so use the Midge Mallet to return to normal size. She may cast Freeze and Acid Storm.
After the battle you get a Whip's Orb.
Go north from where you fought Hexas, then continue north and step on the green switch. You will immediately go into battle with Mech Rider 3. Apparently Thanatos used ancient magic to turn the deceased Geshtar into this living, fighting machine.
Mech Rider 3
If he casts Wall, use Dispel Magic, then attack with Thunderbolt. He only has 38 MP, so you might want to use Magic Absorb to stop him from casting Wall.
After the battle, you get a Spear's Orb.
The Mana Fortress is raised. The coral island sinks again, and you can now see the Mana Fortress floating around in the sky when you fly around on Flammie. Don't fly toward the Mana Fortress yet: you are not ready for it. Land at the Tree Palace below you and talk to Jema. He says that the Mana Beast will soon attack the Mana Fortress, and if you don't stop it, it will destroy the world. But Sage Joch says to visit the Mana Tree in the Pure Land. Usually the Pure Land is blocked by impenetrable clouds, but Mana has become so weak that you might be able to land there now. If you visit the Mana Tree, you could restore the Mana Sword.
Before you go, walk around the back of the palace to find Neko standing in front of the southeast corner of the palace. He is now selling the strongest armor you can buy.
Now you can go to the Pure Land. It is the volcano southeast of the sunken continent. Fly over the green part in the center and land there to enter The Pure Land.