As everyone turns to Fynn, they tell everyone what happened, as they rejoice and celebrate by dancing. Though, it's interrupted by a Retainer that walks in and tells everyone that Leon, the Dark Knight, has claimed himself to be the new Emperor. After some short talking, talk to Princess Hilda, as she learns who Leon is, then memorise Palamecia, then ask her about it to learn that you can't reach it by foot. (Palamecia is that giant castle you saw probably way back when you went to the Coliseum to save Princess Hilda before.) Anyway, ask Leila about Palamecia and she'll mention Pavel might know, so, head out of here and go talk to Pavel now.
At Pavel's House, talk to Cid nearby, as he tells you he was hit by the Cyclone in Paloom. He'll walk over to the bed and he's asked if he's ok, but he mentions his Airship and tells you he'll let you use it until he's better. Though, after saying this, he dies… man, people are dropping like flies, huh? Anyway, talk to Pavel and after he tells you about Cid giving you his Airship, ask him about "Palamecia" and he'll tell you that he used a kite to land on the roof and maybe you can land there with the Airship. So, after this, go ahead sell off anything you don't need, stock up on stuff that you will need and heal at the Inn.
Next up, leave Fynn and head over to Poft and grab the Airship here that Cid left you. Whew, no more walking around or going by Sea, nope, the sky is yours! Whenever you're ready, head over to Palamecia and once there, try and land on the roof and if done right, you'll start the next dungeon.