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, enough to do a number even on Blink-enhanced Characters. In addition, these attacks can inflict Sleep. If you have Spider's Silk, she is a good target for it. Her second most frequently used skill is Charm 9, which is even more dangerous. You'll need Basuna 5 to remove it, and even that won't help if she Charms your white mage. 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.
So what do you do against such an implacable foe? Well, you do have the advantage that this boss fight takes place in town and not at the bottom of a dungeon, allowing you to go in at full power. Offense is probably your best bet here, so spells like Berserk or Curse (or the Ancient Sword) are a priority. The Lamia Queen has no Elemental resistances or weaknesses, so your most powerful damage Spells are also an option. If you have any well-leveled Status Spells, they might be worth a shot, although they'll need to be at least level 4 to have a good chance of breaking through the Lamia Queen's magic resistance.
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.