Matt Bird writes all sorts of nonsense, but he dedicates a large chunk of his time to writing game walkthroughs.
Terra has been located, and though she doesn't exactly look well, she's at least safe. Her overseer, the esper Ramuh, has asked that the Returners free his kin from the Imperial Magitek Research Facility in the Imperial capital of Vector. Celes has agreed to the task, and so, too, has Locke. Looks like you're off to the Empire!
At this point, you need to choose a team to go along with you to the Empire. If you want, you can take only Celes and Locke, though unless your levels are inflated, this is an impractical idea. Choose whomever you like, so long as you have a party of four; all characters are just as good as one another for the trip, in their own ways.
(If you hired Shadow earlier, assuming he didn't leave during a fight, he'll have left at the end of the Zozo trip. If you didn't hire him, you can go back to Kohlingen and get him… though there's not much point. A short way into the upcoming event he'll get bored and vamoose, leaving your team one man light. What a waste of money.)
You need to head to Jidoor to open the path to the Empire. First, though, you should equip your team with the four magicite shards you just received. Each has a different complement of spells, and characters can learn them by earning Ability Points (AP) through winning battles. At the very least, you'll want one character besides Celes to learn Fire, if not all three. You'll know why soon.
You should also note that magicite grant extra bonuses upon level up. These bonuses seem minor, but over time they can add up to significant stat changes. Make sure to take these into account when customizing your characters for different roles.
Honing Your Magic Abilities
Fight a few battles to learn some magic, then return to Jidoor. Visit Owzer's House in the far north and you'll find a man named the Impresario, head of a nearby Opera House. He's in a huff, though he doesn't explain why. Read the letter to learn of his troubles: an airship-owning gambler named Setzer (by default) is coming to steal Maria, the Impresario's lead singer. Leave Jidoor and head south to the Opera House.
Talk to the Impresario and Locke will quickly hatch a plan: use Celes as a substitute for Maria. When Setzer kidnaps her during the next opera, the team will follow him and steal his airship. Perfect plan . . . only Ultros, that slippery purple octopus from the Lethe River, looks ready to mess things up. Nobody notices, though, so this will surely be quite a comedy of errors.
The First Act
Watch the first act of the opera. Once it's done you can walk around as Locke. Visit Celes' room and you can use her to check the score of the opera. You need to memorize certain parts of the opera to make sure Celes performs as required. Step through the curtain at the end of the room to begin the opera.
The first part is the most difficult. You need to remember the initial words to three of the lines Celes is supposed to thing. They run in this order:
'O my hero . . . '
'I'm the darkness . . .'
'Must my . . .'
Once Celes is done singing, approach Draco, the phantom lover nearby, and wander around the balcony with him. Grab the roses he leaves behind after fading and take them to the balcony for one last bit of song. Be sure not to flub any lines or lollygag too long, or the opera will be ruined and you'll have to start over again.
The Evil Plot
Complete the scene successfully and Locke will take over again. Head out of the changing room and you'll find… a letter? Ultros', of course. He's planning to muck up the rest of the opera. Run to the Impersario and tell him and you'll see that Ultros' plans to drop a massive weight on Celes' head, though it'll take five minutes for him to push it off its tenuous perch above the stage. You need to stop him before he can shmuck Celes.
Start by running up and to the right. A stagehand at the end of the balcony will allow you to manipulate the switches here. Hit the far right switch, return to the Impresario, and run to the opposite side of the balconies. The door up to the catwalks will be open.
The Path To Ultros
The path to Ultros is a maze strew with mice. Touch one and you'll get into a battle with Goetias and Stunners. Stunners are a piece of cake, but if you kill them all before you kill the Goetia more will appear. Target the golden rats first, or try to hit them all at once. Try to avoid fighting, if you can—it's possible to kill every rat and still make it to Ultros, but they're just normal enemies and not really worth the extra effort. Reach Ultros and he and the team will take a nosedive—right onto the stage. Some improvised acting later, the fight will be on.
Ultros' second iteration is far easier than his first, as you have him caught in a tidy pincer formation. He continues to use Ink and Tentacle attacks, as well as Acid Rain and L.3 Muddle, the last of which is probably his most dangerous attack (and only if your characters have levels divisible by three). Assault him with whatever attacks you like, though anything fiery will decimate him. Sabin with Burning Fist equipped can eliminate most of Ultros' HP with a single attack. Overall, a complete pushover.
Setzer will show up after Ultros runs away, and true to his word he'll steal Celes. Locke and the gang will follow him, and everyone will confront Setzer on his airship, the Blackjack. With a quick hustle, Celes will convince Setzer to take the Returners to the Empire. (If you have Edgar and Sabin with you you'll also get a funny little scene.) Time to explore another new continent? Yes please.