Welcome to the Airship, an ancient construction that can fly. You don't really get to use it now, but you will later on in the game.
Talk with everyone on the bridge, then follow the path back through the airship and talk to all the familiar faces. Head back to the bridge to trigger a scene with Cid. Talk with Brother at the front of the bridge and he'll say he found Yuna. Unfortunately, she's at the Palace of St. Bevelle, which is basically one of the most fortified places on Spira. So, whilst you get there, talk with your party members once more and equip your best stuff. Try to walk out of the bridge and Rin will appear, telling you that the airship is being attacked from within. Save and head back through the airship once more, and you can enter some compartments to kill some fiends. Once you get to the "top" of the airship nearby the other Save Sphere, talk to one of the Al Bhed to receive Al Bhed Potion x4. Approach the lift to the deck and you'll spot Evrae, the guardian of Bevelle. You're going to fight that thing?! Oh well. Speak with Rin and make sure you buy some Antidotes and Softs (Evrae likes to use poison and petrification, as you'll see) and afterwards you get an amusing scene with Wakka having a go at Rin for actually charging you. Go to the lift and you'll ascend to the top. Approach the blast doors and they'll open. You'll run out, and confront Evrae.
Boss Battle: Evrae
Fighting on the Airship
Before we actually get to killing the giant dragon-esque bringer of death that is breathing in your faces, first you need to know how you conduct battles on the Airship. The quick info screen that appears will give you the information you need to know. Evrae's attacks are based on where the airship is in relation to it, as well as how you can attack it. Up close, anything goes — anything will at least have a chance of hitting Evrae (it's unlikely anything will miss). However, at a distance, only Lulu's magic and Wakka's ball can actually hit Evrae — anything else is out of range (and no, you can't get Rikku to throw a Grenade from that far away). This also applies to the other battles you'll fight on the Airship, which will come at a later stage.
Also, when you're at a distance and it comes to Cid's go, if he hasn't been given an order to move in (or it's been cancelled) he'll use one of the Airship's missile salvos to hit Evrae for 1500-2500 damage. This isn't much but it can help to damage Evrae at a distance since theoretically you're down to 2 characters.
Now, let's talk about Evrae itself. It has 32000 HP, which is second only to one creature you've fought so far, which is the Sand Worms you may have encountered in Sanubia Desert. Unfortunately, Evrae's significantly more powerful than them, so you're in trouble. He halves all elemental damage. Up close, Evrae has 3 attacks of note — a claw attack which does about 1200 to one person, Stone Gaze which petrifies one person, and Poison Breath which he will unleash on the turn after he inhales (tips his head back and doesn't seem to do anything) which does about 1500 to everybody and inflicts poison. As you can tell, this is a deadly attack (although one an Al Bhed Potion seems to remedy remarkably well). From a distance, he has Photon Spray, which does 8 or so random hits of about 100 damage to everyone, and Swooping Scythe, which does about 700-800 damage to everyone and automatically brings Evrae closer again. Outside of this, Evrae may also use Haste on itself (this gives it a terrifying amount of extra turns).
It's time to knock this thing out of the sky for good. The first thing you should do is have Tidus in-battle and use Haste on himself. If he has the Sonic Steel equipped he'll get the first two turns, one of which should be Haste on himself and the other should be Delay Attack/Delay Buster on Evrae. Tidus should then continue to cast Haste on other party members. Wakka should be the next to come out, to use Dark Attack on Evrae. Keep using Dark Attack until it succeeds (Evrae has a resistance to it). Auron should come in as well, and have him use Power Break. Get somebody with a Sensor weapon out to see if you've inflicted darkness and Power Break. Once you're happy with that, bring the Airship away from Evrae by giving the order. Tidus should stay out and replace Auron with Lulu. You also need to make sure everyone gets a turn, so have Kimahri come out and use Lancet and Rikku to use Luck or a Mega-Potion if necessary. Wakka should continue to attack Evrae and Lulu should use -ara spells (Bio doesn't work on Evrae). If you're up close and Evrae inhales for Poison Breath then give Cid an order to move away as soon as possible. Poison Breath will always be Evrae's next non-counter-attack after inhaling and it won't hit you from a distance.
Once Evrae gets down to 10000 HP it will automatically use Haste. It will counter Slow attempts on it (which work about 50% of the time) with Haste. It may very well counter a physical attack with Haste. Now Evrae becomes much more difficult. Get Tidus, Rikku and Wakka out. Tidus should use Cheer and heal, Rikku should use Luck and heal, and Wakka should attack until Evrae uses Swooping Scythe (again, which it might use as a counter-attack). Now, with the amount of turns Evrae gets avoiding Poison Breath is impossible, or if you can manage it, Evrae will counter any action you take at a distance with Swooping Scythe and then unavoidably sneak in a turn and use Poison Breath. This is really cheap, but sadly there's not much you can do about it. In conjunction with Swooping Scythe, Poison Breath can do between 1800 and 2300 damage to everyone, which is enough to easily put everyone in critical. Rikku should be out now to use Al Bhed Potions as much as possible. Evrae may randomly decide to counter-attack one move with two attacks (i.e. you attack it from a distance, it uses Haste, it uses Swooping Scythe, then it uses Poison Breath if it inhaled, or Stone Gaze or a physical attack). It may, also, if you're really unlucky, counter an attack with inhaling, which really sucks.
One last thing to watch out for is that you make sure you remedy any status immediately after getting it — if Evrae uses its claw attack on someone who's petrified and it connects, that person will be shattered, and you'll lose one party member slot and the character that was petrified for the remainder of the battle. Fighting Evrae with two people as opposed to three is nigh on impossible unless it has about 2000-3000 HP left. There is no doubt that Evrae is much harder than anything you've fought so far, especially without Yuna and her summons. Oh well.
Once Evrae's down you'll leave the airship and land on Bevelle, the Priest's Passage, ready to confront Seymour.