The first order of business is to definitely sell off any Items you don't need and to stock up on anything you do need. Also, make sure you rest at the Inn and stuff, then when you're ready, make sure you remove all of Leila's Equipment, as she'll be leaving you for a little while. Then, go ahead and enter the Rebels' Hideout and once inside, head to the door that's in the southeast area of this place and enter it to find Princess Hilda. Talk to her and she'll want to talk to Firion alone. Everyone but Firion leaves then, as she starts to come onto Firion. A bit perplexed, Firion goes with it, as Princess Hilda apparently isn't who she says she is and attacks Firion, just as everyone comes in to help you. At this time, you'll enter another Boss Battle, so, if you need a strategy, head to Section VII. Boss Guide now, otherwise, fight this yourself and move on.
After the Battle, Firion thanks Leila and everyone for coming to his aid, as a Retainer enters and tells you about a tournament in Palamecia being held and Princess Hilda is the prize. Just then, Gordon enters and tells you he's going with you, as Leila decides to stay behind and guard the place. Gordon rejoins you now, but he won't be with you for long, so really, don't bother with him. Anyway, Palamecia is located near Castle Kai'son, but it's across a desert with some VERY powerful Monsters. If you look on your Map, find Castle Kai'son and see the desert to the south? To the east of the desert is Palamecia, so, you have two choices. One, you could go to the Chocobo Forest and ride a Chocobo there, Battle free or you can land to the south of the desert from your Ship and walk there, getting into Battles to fill up your Bestiary List.
It's your call on what to do, but either way, make your way to Palamecia when you're ready and once there, go ahead and enter it.