The next destination is the “weird-looking structure” - the city of Esto Gaza which you may or may not have been to previously, depending on how much exploring you did when you gained access to the Blue Narciss or depending on how closely you’ve been following this guide.
Close to where the Blue Narciss docks though are some Chocobo Tracks. Wander around this area until you run into another Friendly Monster named Feather Circle.
The Feather Circle is part of the Friendly Monster side quest. Click on the link for more information.
You can take this opportunity to deliver another Kupo Nut to Mugato in Gizamaluke’s Grotto to receive another random item. This is part of the Kupo Nut side quest.
Lastly, take this opportunity to complete the Chocographs side quest and do all of the Chocograph hunting that is available at this point in the game if you have not done so already. If you have been following this guide though then you should be all caught up and there are no further Chocographs for you to find.
Note that Chocograph #15: Dusk Plains, Chocograph #16: Forgotten Plains and Chocograph #22: Outer Island 2 are all still unobtainable for now.
At this point in the game you will find that you are in a tough spot when it comes to healers and Wht Mag spells. Eiko is now missing and Dagger continues to struggle with her ability to concentrate, causing random attacks and spells to fail in battle. Your best bet at this point is to add Quina into your party and to use Quina’s Blue Magic spell “
White Wind” to heal the party.
Vivi also becomes extremely powerful at this point in the game due to some weapons he now has at his disposal (assuming you have been completing the side quests along the way). The 
High Mage Staff or 
Gaia Gear can be used to teach him Osmose and he will soon receive a staff in Mount Gulug that will teach him his most powerful elemental attacks (specifically Firaga, Blizzaga and Thundaga). It is also recommended that you include him in your party.
Enter Esto Gaza and some cutscenes will take place inside the entrance. The Bishop will tell Zidane and his party that Kuja and the Black Mages passed through Esto Gaza and had Eiko with them. There are a ton of new items available at the Esto Gaza Shop this time around including:
Gladius
Zorlin Shape
Diamond Sword
Flame Saber
Heavy Lance
Scissor Fangs
Magic Racket
Asura’s Rod
Hamelin
Cypress Pile
Octagon Rod
Silver Fork
Rising Sun
Egoist’s Armlet
N-Kai Armlet
Jade Armlet
Diamond Gloves
Venetia Shield
Black Hood
Red Hat
Cross Helm
Judo Uniform
Power Vest
Gold Armor
Shield Armor
Make sure you have a fair number of 
Vaccines in your inventory as well in preparation for an upcoming dungeon. There is also a hidden Wing Edge on the right side of the shop behind the counter. Exit Esto Gaza out the back going down the same pathway that Kuja and the Black Mages took.
Speak to Mogrika the Moogle to pick up a letter from Artemecion to Mogrika. Speak to Mogrika again using the Mognet option to pick up a letter from him to Moolan. Save your game and then continue down the pathway.
