The Temple is an impressive structure to say the least; four giant stone heads surround the walkway up to a huge pyramid. Bellena stays outside while the rest of your party resolves to find the Moon Crystal, as well as whatever other loot they can find.
Head up the steps in front of you, past the odd-looking pedestal, and up the huge staircase beyond. There's a save point at the top which you can use, then head through the big doors into the Temple itself.
Go down the corridor in front of you, and walk onto the barrel on the left. Keep pushing forward and Vyse will roll it across to the other side; this is a pretty important puzzle mechanic later in the dungeon. Go down another long slope and head along the walkway here until you come to a ladder, then climb down to the next level. Follow this ledge along to another ladder and climb down again, the take this path along to a doorway.
As you approach it, the camera angle will switch to show you the boulders rolling down it periodically. Needless to say, you want to avoid them, so wait until one has rolled past, then run down the slope. About halfway down, there's a door on the right (Vyse's left) marked by a set of torches on the wall.
Run up the slope all the way to find a chest - when you open it you'll be thrown into a battle against three Magma Tiki enemies, so patch anyone up who needs it first. Purple weapons and magic are most effective, and you'll be rewarded with the chest's contents, an Ancient Robe, when you defeat them. It's worth pointing out that all the chests in the Temple of Pyrnn are guarded by a trio of Magma Tikis.
Go back to the rolling boulder corridor and go all the way to the bottom when it's safe, and you'll come to the first barrel-rolling puzzle.
You'll need to roll the barrels at the sides into position first; they'll plug the first two holes, allowing the barrel at the end to roll over them into the third position. Plugging all three holes will unlock the door, but if you mess up and need to repeat the puzzle from the start, just leave the room and come back in.
Through the exit, go down another slope to find a chest with three Sacres Crystals inside. Take the exit to the right to find another chest, with a new boomerang for Aika in it, the Dancing Arc. Head all the way north for a third chest containing 774 gold.
From there, go south one room and then west twice to get a second barrel puzzle, which is the first to have colored barrels. Roll the red barrels in first, then the blues to unlock the door, which leads to another rolling boulder corridor. Again, halfway down there's a corridor to the right (Vyse's left), but this time there's also a Cham in an alcove opposite it. Once you've picked it up, go through the doorway opposite and follow the corridor all the way to find a chest containing a Moonberry.
Return to the boulder path and go down to the bottom, then through the door into a magma cavern. Follow the walkway through here all the way to the bottom - there's a chest on the middle level containing five Magic Droplets - and through the door.
Ignore the switch in front of you for now; head up the slope to the right and follow it left, all the way to the end. There's a chest here, guarded by Zivilyn Bane - a treasure hunter who's after the chest's contents. Bane is aligned to the Red moon, so as with most of the enemies in the Temple it's best to use Purple weapons and magic. Aika and Fina should use Crystales while Vyse attacks normally. Your reward for defeating him is the Rune of Ill Omen, which can be sold for a lot of gold when you get back to a town.
Head back along the walkway and go down the steps about halfway along to find a final rolling barrel puzzle, made more difficult by certain parts of the floor rising and falling as barrels drop into the holes.
First off, roll the barrel in the top left corner into the top middle hole. Next, move the bottom right barrel into the hole directly in front of it, and do the same with the bottom middle barrel. The middle left barrel can now be rolled all the way across the board to the hole directly in front of the red barrel, allowing the red barrel to be rolled into the central hole.
Head back down to the switch you saw earlier and use it; a torrent of water pours down and solidifies the lava, which means you can now walk across it to the save point. Equip Fina with the Gem of Fluidity you got from Maramba's underground tunnels - it will prevent her from being Petrified by the upcoming boss, and since she's likely to be the only one with the Risan spell so far, it's best to make sure she'll be able to move if its needed.
Make sure everyone's healed up with as close to full MP as you can manage, then save and head through the door.
Rockwyrm
Equip everyone with Purple weapons for this fight; the Red Moon-aligned Rockwyrm will take a lot more damage that way.
Use Aika to Focus, which will build SP for Vyse's Cutlass Fury move - or if you've learned it already, Pirate's Wrath. Cutlass Fury is a little better however; the time taken to build up the 21 SP for Pirate's Wrath leaves you open to attack a lot.
When you haven't got the SP for a special move, use Vyse to attack normally. While he won't do all that much damage, chipping away little bits of Rockwyrm's health will make things easier in the long run.
Fina should be used to heal the other party members; use items as much as possible to save SP for Vyse. Likewise, if you've got any Crystales boxes, which can be used to cast the spell without requiring MP or SP, they're hugely effective against this boss.
With the Rockwyrm defeated, run across its back to reach the other side of the lava pit and go through the door to find the first Moon Crystal.
Back outside, save at the top of the steps before running down to meet Bellena again.
Unfortunately, it seems you've all been duped: the Nasrean dancer is in fact Belleza, one of Valua's Admirals, in disguise. Ignoring Fina's pleas to the contrary, she places the Red Crystal in the pedestal, awakening the Red Gigas Recumen, and ordering it to destroy Vyse, Fina and Aika.
As the three run across the desert in an attempt to escape, the Gigas powers up an attack and fires - but a cannon impact throws off its aim at the last second, causing Recumen to miss its target. Drachma's come back, and is ready to help Vyse take down Recumen.
Recumen
The main focus of your actions for this entire fight should be healing. Recumen's main attack, Red Ray, can cause upwards of 6,000 HP damage when it hits, but fortunately it takes a couple of rounds to charge it up. You can throw the Gigas off balance by firing on him just before it performs the attack (the red turn in the battle grid), but even that can be hit and miss.
This can be an extremely tough battle to win if you're low on Repair Kits and MP. Often, the Sacres spell's 8,000 HP repair can be more helpful than the 4,000 offered by a Repair Kit, but save it for just after the Red Ray.
After several rounds, Drachma will recommend a strategic retreat, while you formulate a better plan of attack. Accept his proposal and the battle with Recumen will end.
Fighting the Gigas itself doesn't seem to be very effective, but Fina points out that Recumen is only doing what it's told to by the person holding the Moon Crystal. Aika's figured a way out, and you'll get a Swashbuckler decision to back her up - the correct answer is "You mean, attack Belleza's ship?".
The Lynx
Belleza's ship is equipped with a number of nice new weapons you won't have faced before; Magic Cannons allow her to cast offensive magic on your ship, while Secondary Cannons and Torpedoes allow her to attack multiple times on the same turn.
For the first couple of rounds, have Vyse and Drachma attack, while Aika and Fina Focus, and heal when you need it. Keep your health as high as possible, occasionally the Lynx will hit you with three attacks at once, which can be devastating.
After a while you'll get a choice of attack plans, which will affect how the next couple of rounds go. Pick the second option, "Turn hard and try and catch her off guard" to get slightly easier proceedings. Keep the same strategy as before for the next few rounds, then you'll get another choice - pick "Set engines to full speed and get behind her".
For the next couple of rounds, the main aim should be Focusing to build up the 15 SP required for the Harpoon Cannon, although you can keep attacking occasionally. You'll get a third set of options after another couple of rounds; choose "Head straight upward!", and then use the Harpoon Cannon when you've got the clean shot to use it.
As a reward for beating Belleza, you'll get a Captain's Stripe and a 3" Blaster Secondary Cannon, as well as a Magic Cannon which will allow any Main Cannons equipped on the Little Jack to use offensive magic.
With the Lynx down, Belleza hands the Moon Crystal back to Vyse. The next step for the Moon Crystal search is Ixa'Taka, to the south under the Green Moon. You'll need a special type of engine to get through the tornadoes of South Ocean, but fortunately Belleza's ship has one that you can use. That'll leave her stranded in the desert, but none of your party seems particularly bothered by that idea.