Return to Altair
You have several options for how to reach Altair from Castle Deist. The shortest is to sail directly east, possibly following the coastline south some distance. Be careful landing the ship too far south, though, as due west of Altair you'll find dangeous monsters from the Mysidian Tower Area. It's safer to land west of Fynn and travel the rest of the route on foot.
Alternately, you could sail back northwest, through the strait, and back to the inner sea, landing on Altair's east coast. This gives closer access to several towns, and leaves a route of similar distance for your next destination. Importantly, later in the game you will have to return to the inner sea anyway, so doing so now may be worth the longer trip.
Altair
After you return from Castle Deist, having submerged the Wyvern Egg in the spring at the bottom of Deist Cavern, things are amiss with Hilda in Altair. When you speak to her, she will reveal herself to be an impostor, a powerful Lamia Queen you need to defeat.
Every action the Lamia Queen can take is bad news. Just over half the time she'll make eight powerful and accurate attacks that can inflict Sleep. Her second most frequently used ability is Charm 9, which is even more dangerous. You'll need Basuna 5 or a Unicorn Horn to remove it, and even that won't help if she Charms the characters equipped to do so. Finally, and mercifully rarely, she can use Blink 16 to enhance her physical evasion to the point where you'll need to rely on spells to get any damage through. Her 1,290 HP ensures that the battle will take a while whatever you do, giving her plenty of opportunities to ruin your day.
The good news is that this battle takes place in Altair, allowing you to go in at full power and reload quickly in the case of a loss. There's little you can do to reliably defend your characters, so concentrate on offense. Berserk and the Ancient Sword can help end the fight quickly. The Lamia Queen has no elemental resistances, so your most powerful damaging spells will help. Status ailments can be effective, but you'll need one at level 4 or higher to have a good chance of landing it. A Sage's Wisdom or Saint's Spirit can make your spells significantly more effective as well.
When you do win (hopefully earning one of the Lamia Queen's amazing potential drops), Leila will leave the party, replaced by a returning Gordon. Don't worry about unequipping her, as she will return with the same stats and gear a bit later in the game. Gordon returns in the state he originally left you, and likely needs an equipment refresh. He won't be staying in the party overly long, though, so don't worry about his combat prowess too much.
With the fake Hilda defeated, the Emperor reveals that the real Hilda was captured and is being offered as a prize to any who would fight at the Coliseum. Found in the shadow of Castle Palamecia, this is your next destination.