Phoenix Summon Location and Guide
When you get your Airship back on World 3 you'll be able to complete the sidequests for both the Phoenix Summon as well as the Bahamut Summon. You won't be able to access either of these locations with your Airship though, instead you'll need to fly your Airship over to Mirage Village and get the Purple Chocobo from there then fly the chocobo to the desert where you can find Phoenix Tower and North Mountain.
If you're wandering around lost in Mirage Village looking for the Purple Chocobo, I recommend you read my Piano Master Guide since that goes into much more detail about how to reach the Purple Chocobo in this town. Once you've obtained the Purple Chocobo you'll want to fly to the northeastern most portion of the world where the big desert is. Use my map below for some extra guidance.
You'll land somewhere around the middle of the desert, to the north will be North Mountain and where you find Bahamut. Down south is where we're going which is where you'll find Phoenix Tower and the Phoenix Summon. While traveling through the desert on your way to the tower, I recommend you keep yourself well healed and your MP up since the enemies you encounter here aren't pushovers in the least.
Phoenix Tower is a rather difficult dungeon for a few different reasons. The first of which is the enemies here sometimes inflict status ailments onto your party & you can't run from the battles. Second reason is, the Magic Pot enemies in this dungeon which you can feed Elixirs to for 100 AP each typically make you run through this place with crappy Jobs to level them up easily.
Before you go into this place, you'll need to decide if you're going to ignore the Magic Pots or feed them Elixirs. There's 4 or 5 Magic Pot enemies throughout the dungeon and it won't take more than 25 Elixirs in total to feed them all, which'll net you 400 - 500 AP from just those fights! The only reward from these fights is ABP so if you're not leveling up Jobs fighting them is pointless.
The way this dungeon works is fairly straight forward; there's about 30 floors and each floor of the dungeon either has a visible staircase or it doesn't. When there's no visible staircase you need to inspect the southern wall to make it appear. If you inspect the wrong spot on the wall, you'll have a fight an enemy.
Below you'll find a list of each floor with a hidden staircase on it as well as the side of the wall you'll need to inspect in order to uncover the stairs. There is no Save Point or place to rest throughout this dungeon so be prepared before you enter to go through all thirty of the floors in a row.
At the top of the dungeon you'll be treated to a flash back scene with Lenna in it. You'll be given the option to cut out the Dragon's tongue or not, it doesn't matter which option you choose you'll still get the Summon. If you choose to cut out the Dragon's tongue, Lenna's father will bitch slap her across the balcony and scold her. After the scene, you'll be rewarded with the Phoenix Summon!