Make any preparations before heading out of Kakkara Village. In order to find the Fire Palace quickly, you must think back to what some of the Sandship soldiers told you: to go west. Heading out of the village, going west isn't an immediate option. You must choose between south and east. Take the south exit, and you'll arrive in a region of the desert where west is an option. Taking the west exit doesn't bring you to the Fire Palace, but it gets you close. The path that leads to its entrance can be found by heading north.
Follow the entrance path as it climbs up a hill, past some Sand Stingers. You're also likely to see Robin Foot enemies up on an isolated section of land, but you can still strike them with throwing weapons. Enter the palace itself, where you'll be greeted by two more Robin Foots. From here, there is a path straight up which is blocked off. There is a door to the right, but it leads to a room with a switch that's inaccessible from your current direction. Your only real option is to take the door to the left.
This door leads to a small path with a Robin Foot. Fight past him and follow the path down to the stairs below. In the following room, you'll find it incredibly hot. The screen will get considerably red, making it difficult to make certain details out. The room is guarded by Dark Funks, the fire equivalent of the snowy LA Funks from Ice Country. If you look around, you should notice a crystal orb in the room. If you analyze it with the Girl's Sylphid magic, it will report being susceptible to Salamando's magic. Have the Sprite cast Exploder on it, and the flames will die down. This will allow you to search around the room and find a staircase in the upper right corner.
Climbing the stairs leads you to the lower right corner of a room with an overwhelming number of options. It contains many Red Drops, and like all drops they multiply up to a maximum of three on the screen at a time. Don't get consumed trying to fight them unless you're grinding for more experience points. The upper left and upper right paths both lead to dead ends. The lower door in the middle returns you to the palace entrance on a one way trip downhill, so avoid it. That leaves the lower left door and the upper central door.
The lower left door leads to the upper region of the room where you fought a Robin Foot on a narrow path. Another Robin Foot guards the upper path, which leads to a chest that happens to contain 1000 Gold. Exploring the upper left door simply leads to a dead-end. Return through the upper right door, and this time take the upper path in the middle of the room.
You'll arrive in a room with another narrow path, guarded by a Robin Foot. A crystal orb sits off to the left. If you analyze it, it also reacts to Salamando magic. Have the Sprite cast Fireball magic on it, and a path will appear to your right. Follow it down, and over to the right. Before you explore the staircase at the end of the path, head up and examine the doorway at the top to find a room with a chest that contains another 1000 Gold. Then return back down and investigate the stairs.
They lead to a new room composed of three rows. Dark Funks and Mad Mallards occupy this room. Freeze works very well against the Dark Funks if you're trying to remove them. From where you arrive, walk to the left and take the staircase that leads to a room below. This room contains many alleys that you have to navigate all of your characters through, first through the middle and then all the way to the right. If one gets stuck, it may be difficult to reach the top. Fight your way past a few Robin Foots, and you'll find a treasure chest at the top. This chest contains an Axe orb. Collect it, and return to the stairs at the bottom.
Back in the previous room, head to the middle of the row, and run down the central corridor to the very bottom. Then head left and back up to access the stairs that you find (marked K on the map). This will bring you down to a room that head down before passing through a door to a path that winds its way up, to the right and back down. Follow this path all the way to reach a set of stairs. These stairs deposit you on the other side of a room with a switch that you couldn't access previously. You can now, so make sure you head to the left and step on the switch. When it turns red, return to the right and head down, right, and up.
This will bring you to the opposite side of the room you were just in. Fight past a Robin Foot, and climb the stairs. Use your whip to get across the gap, climb back down, and access the staircase to the left. Immediately take the next staircase above and to the left. This puts you in a large room with many fire pits and a single green switch in the middle. Step on the switch, and the pits will light up. A crystal orb will also appear on the altar. If you analyze it, you'll learn that Undine's magic works. Cast Freeze on it, and all but two pits will extinguish. Step between those two pits, and the alter will be replaced by another set of stairs. Climb the stairs to enter an empty room.
At this time, a boss will appear. This boss is the Minotaur, a powerful fighter with the ability to cast a high level defense spell on himself. Analyze him to learn his weakness. Minotaur fears Sylphid, so have the Sprite cast air attacks at the Minotaur as frequently as possible. If you've leveled up your Sylphid magic, it actually won't take more than a couple of spells to put Minotaur out of commision. If not, or if you're out of magic, you've got a bit of a fight ahead of you. Minotaur likes to walk up to your fighters, pick them up, and throw them around. Attack from a safe distance if possible.
Once you've defeated him, victory will net you a Javalin orb. If you've found every orb so far, including the Axe orb hidden in the palace, these will bring every weapon in your possession up to level 4. Head up through the door at the top to reach the room where the Fire seed is kept. Walk up to it to touch it and recieve its power. You will now be able to level all of your magic up to level 4.
At this time, you must exit Fire Palace, either by backtracking your way through the now empty hallways, or simply using the Magic Rope. Return back to Kakkara Village (South, West, North, North) where the inhabitants will be greatful for your deed to restore the seed, but lament the fact that they still do not have any water. The village elder mentions the Sea Hare's Tail. If you head over to the Cannon Travel center, a third option will now appear among the choices. Besides Matango and Ice Country, you may also choose to travel to The Empire. Although dangerous, with no other lead, this should be your next destination.