Altair
Return to find Gordon and you will find out that Princess Hilda has been acting weirdly lately. He asks if you could speak to her. She is in the bottom right room within the same house. Before you enter the room, unequip Leylia's equipment if you do not want to lose her equipment as she will leave you after this section. Speak to Princess Hilda and she will try to seduce Firion. But she turns out to be a monster serpent. The rest of your party will enter the room and defeat it to find out that Princess Hilda has been captured by the Emperor. He is offering her as the prize at the Arena's fight. Leylia will leave you and Gordon will take her place. Head west from Altair to find the Arena in the right side of the Desert.
Arena
Enter the Arena and you will find yourself trapped by the Emperor. He will trap you in the arena area to fight a monster. After you defeat it, you will head towards the Emperor but he will disappear and set his soldiers upon you to capture you. You get thrown into jail but someone will come to release you for helping him escape from the mines. Search all the rooms within the area to gather all the treasure boxes and go upstairs from the top right corner.
Unequip Gordon before you enter the room containing Princess Hilda as he will leave with Princess Hilda after you open the door. Leave the Arena and head back to Altair to find everyone gone.