The Garamsythe Waterway
There's a save crystal here, save an heal up here if you like. Climb the stairs and follow the path - this section is relatively straightforward, so just head north and right on your map. Continue east, you'll reach a sort of shallow-water area, keep your eyes peeled for chests and what have you - you can level up and gain a few bits of loot from the rats and other monsters that hang around here.
Cross the bridge and up the stairs, one path leads to a dead end which may have a chest that has a high enough chance of containing a Mage Masher, it's entirely up to chance.
Head up to the northwest corner of the screen, enter the Royal Palace of Rabanastre.
The Royal Palace of Rabanastre
Grab the map from the urn, save your game at the save crystal and go through the door. Don't touch the two chests to your right (in the south-west corner) unless you don't want to get the Zodiac Spear. Chat to some of the servants to garner some clues to solve an upcoming puzzle. If not, make your way to the stairs.
A cutscene will trigger once you get near the Imperial stormtroopers, then afterwards speak with the Imperial. Another servant will observe this, speak to him, then press square to lure an Imperial to come towards your new friend.
Now's your chance! Do a long curve around where the Imperial is, then dash up the stairs - it's pretty difficult to get detected, and even when you do go out of your way to get caught all that happens is you get sent back to where you started with the servant. You're now up in the Lower Halls.
The Lower Halls of the Palace
Somewhere around here is a big picture on the floor which has a lions head on it. Apparently that despite several advances in technology one must lock away their treasure by means of time consuming and costly cloak and dagger tricks in their universe.
The gist of this mini-game is that you have to lure the Imperials away and run towards the crest. If you get caught, all that happens is you get chucked back to where you started. Gee, these Imperials are great on security. Maybe they could give Darth's Stormtroopers a few pointers. Press square to lure them away, and some don't move at all for some reason. Maybe they just dressed some mannequins up as soldiers to scare people off - it'd sure cost less.
You want to get to the top path that's in the middle, but go ahead and look at the Hawk crest that's in the path ahead of you when you first enter.
It isn't very difficult to solve this puzzle on your own, you just have to yell stupid phrases at the guards (marked on your mini-map by aesthetically pleasing green dots). You have to run to the Hawk crest, yell at the guards for them to run after you, run away from them. Go back the way you came, taking the right fork and run down the long hallway to the path past the one with the Hawk Signet. The Lion signet is down this hall.
Once you get to the Signet, go and use the Crescent Stone for something to happen. Note that if you get caught by the guards from this point on, you won't have to keep using the Crescent Stone.
Call the guards, then run to the next hall and do the same. You'll do it again on the next hall, then run down the next one on the right. Your path should be clear, until you find an alcove in the north-west that has a faint glow emanating from it. Agree to approach the wall and enter the aptly-named Secret Passage.
Continue through the passage to the end and press the switch on the wall to your left, you'll hear a click. Turn around and look at the wall that has the caption 'Suspicious-looking wall' on it when you get close to it and choose to examine it.
There's another cutscene here, and you get introduced to the apparent 'leading man' of this tale and you get the Goddess' Magicite. More cutscenes and yabber, and you next have to go up the Garden Stairs, keep going up until you get a cutscene, and sit back and watch the pretty fireworks in this huge cutscene. Also, Fran and Balthier join your party.
Back to the Garamsythe Waterway!