To start with, head up the stairs until you reach the cracked ground. For future reference, a sealed crack is one you can step on once, and one with a small hole is one that you will fall through if you step on it (obviously you'll just jump over the huge holes). Step on the crack with a hole to fall down, then head south out of this cavern. You'll appear outside where you can get the chest blocked off by a rock—a Full Metal Vest. Equip this on Felix. Go back into the cavern and head up the stairs. Leave this area to the right.
The pillars here serve similar purposes to the cracked ground—a solid pillar is one you can jump on, but leaping onto a cracked one will cause it to break and you to fall. Use the pillar at the top to reach the chest with the Elixir on it, then climb back up the vines and leap across the other two pillars to the other side. Head south, and follow the path until you reach more cracked ground. Head up to the crack with a hole in it near the top and fall down it to reach a Mint in the chest below. Mints increase Agility, and Felix will be your slowest party member, so use it on him. Drop off the ledge using the groove to the left, then climb up the vines and follow the path to exit the cave. Shove the pillar off the cliff and leap back across. Back at the cracked ground, head up to first big hole and jump across it to the right, then walk up across the sealed crack and exit the area to the north.
Jump across the solid pillar to the rock, then jump on the pillar to the left to reach a smaller rock. Jump on the pillar that goes nowhere to crack it, then jump back on it to break it and fall. You can now climb up the vines to reach a chest containing Themis' Axe, the first in a very long list of special weapons. Equip it on Felix, and then leave the area to the south, then return to reset the pillars. Jump across the first pillar again, then use the bottom chain of pillars to get across to the left-hand side of this area. Use the pillars to get around the rock, then follow the path around the top and exit the area to the east.
In the next area, fall down any of the cracks and exit the cave below. Cannon the Mars Djinni will be up here, and will try to escape, falling down another crack. Follow its lead by dropping down another. Exit the cave and go down to the vines. Climb up, and when you reach Cannon it'll run off to the right. Shove the pillar off the cliff here to open up a shortcut (which you may very well never need) and then follow Cannon to the right.
Pursuing Cannon
Chase Cannon across the bridge (hop the gaps). When you reach the other side, it'll use Pound on the weird-shaped pillar (most of which were stopping your easy exiting earlier on) then crack a piece of ground before running off to the right. You can't follow it, so head back across the bridge, climb down the vines and go across the two ropes. Shove the first vine-covered pillar to the right two spaces then climb up it and use Lash on the rope on the top. The chest contains a Nut. Head back down and shove the other vine pillar off the cliff, then climb down it. At the bottom, head to the left underneath the rope. Climb the vines.
You can't follow Cannon across the pillars, so instead climb down the vines. Use the vine pillar to get up onto the rock, then use the pillars to crush the left-hand pillar so you can get past it. Go around, move the vine pillar across, climb up it, and then leap onto the cracked pillar to break it. Climb up the vines, shove the pillar off, climb back down and move it across one. Climb back up and use it to get across to the door. Enter it and follow the cave through until you can see Cannon again. If you try to approach it in any way here, it will use Pound to smash you through the floor. Instead, cross the room and leave it to the right. Go up the stairs, then go up to the cracks. The one in the middle of the circle of rocks is the one you want, so fall down it.
You'll land on top of Cannon, relieving it of its Pound Cube. Go and pick it up, equip it on Jenna, then follow it out of the room. Go through the next one, and in this next room, if you try to go to it, it'll leap across the pillars, cracking one on the way, and it'll be out of your reach (until you leave the room). Instead, climb down the vines and use Pound on the weird-shaped pillar. Now it can't escape. Approach it and fight it.
Cannon, the Mars Djinni
Now you might want to consider using Mercury and Fog. First turn, have Felix use either Echo or summon Venus, Jenna should summon Mercury and Sheba should summon Jupiter. If it runs, just leave the room and repeat. Next turn, Felix should either attack or use Venus if you unleashed Echo last turn, Jenna should attack and Sheba should cast Ray. Either Cannon will be defeated by this, or one more turn of attacks should finish it off. Give it to Jenna, Set it, and then put Fog on Standby.
When you're done, climb down the vines and climb up the other side. Follow the stairs and the path up until you're outside again. Go down the stairs (you can go up some others to open a shortcut) until you can leave Dehkan Plateau.
On the world map, head down to the familiar-looking ship on the beach here.