Well, as your party comes to, they see they're inside of a creature and that Leila is missing. Afterwards, you'll have to escape Leviathan, the thing that ate you, so, head north through the gastric juices, which will hurt you for 1 HP per each step and follow the path around and grab the Treasure Chest you see to get a Headband. Give this to Firion and give his Gold Hairpin if he has it Equipped to whoever you wish. Next, continue on and grab the next Treasure Chest you see to get a Power Sash, which, give this to the person with the crappiest Armour at the moment, as it should boost their Attack and Defence. After this, continue on the path and then enter the "door" nearby. On this "floor", just follow the path and grab the Treasure Chest you see to get a Power Armlet, which, give this to Firion.
Then, go and talk to the man guarding your path, as he asks for proof of who you are. Show him the Crystal Rod, as he sees you're going after the Ultima Scroll. He'll join you, wanting to get out of here together, so, welcome Gareth to your group. (Note: His name was Richard in the original version… I don't see WHY they changed it…) After this, Equip Gareth with anything you want, since he'll be with you for a little while. Next, just head west and enter the "door" here and on this "floor", head west and open the Treasure Chest here to get a Terra Sword. Give this to Firion or whoever your Swordsman is, then head south and grab the Treasure Chest here to get a Diamond Shield, which is guarded by Shriekers. Give this to Firion if he can take it, otherwise, anyone else will do fine.
Next, head west to find a Barrel Worm and once you talk to it, you'll enter a Boss Battle. If you want a strategy, head to Section VII. Boss Guide now, otherwise, fight this yourself and then move on. After the Battle, go ahead and get on your Ship to leave this hellhole. Back outside now, if you need to, go and heal up and whatnot, then head over to the Mysidian Tower, where you were originally trying to reach. Once there, examine the tower, as a scene takes place and you head inside.