There are very few pathways to take from Gongaga next; the only real way lies west, over the river to a mysterious place that tends to live in eternal twilight. It's hard to miss as the game throws some really big hints toward you that checking out Cosmo Canyon would be a good idea. Among other things, if you drive past the town in the Buggy, it will break down, leaving you at the mercy of the local mechanic.
Red XIII, whose name you find out is Nanaki, joyously goes to see his grandfather. This turns out to be a 130-year-old, legless, hovering man called Bugenhagen. This place is full of mysteries.
There isn't a whole lot to do in Cosmo Canyon right now. You can visit the Shildra Inn (which has one of those Turtles Paradise posters of #5) and pick up an Elixir by the couch after staying there. Or you can shop for all-new weapons and silver armlets. Aside the Shildra Inn poster, there's also another Turtles Paradise poster #4 in the Tigerlily Arms Shop after learning of Red XIII's heritage and his shame, proceed further up, and you'll encounter another materia shop which also sell some new materia!
Once done, climb all the way to the topmost building, where Red XIII is talking with Bugenhagen. Red XIII wants Bugenhagen to show you his contraption, and for that, you need to hunt down two party members. Your party is scattered throughout the city; Barret, Yuffie, and Cait Sith are in the rooms in the mountainside, Tifa and Aeris are in the bar at the inn.
Once your party is selected, head back up. Bugenhagen will show you his holographic planetarium, and lecture you on some of the basics of the game's backstory. Basically, Mako-sucking technology is evil and the lifeforce in every living being is really good. After this, everyone will retreat to the Cosmo Candle, the big bonfire in the lower plateau. You need to talk to everyone here. Barret wants to rebuild AVALANCHE, Aeris thinks of how alone she is, and Tifa seems strangely lost in thought, thinking of the past again. Lastly, you need to talk to Red XIII, who seems to be pretty mad, because he thinks his father was a wimp. Bugenhagen seems to disagree - and intends to show him exactly what the truth was.
Cave of the Gi
You probably noticed a steel door that was closed down and some kid was wondering what kept it in place. Your party will now consist of Cloud, Red XIII and one character of your choice. If one of your goals is the Master Materia, you should choose Cait Sith: in this area you'll find his Black Megaphone, the first of the materia-growing weapons in the game. Bugenhagen will follow you from a distance, but doesn't participate in any battles.
After the door, there's a long descent down, then a big cavern full of little caves. Each of the caves has a rock. If you hit one, you either get a bunch of not too happy Gi Spectors, or the other cave opens up. The one you need to hit is the one nearest the wall up there, but don't worry too much about the battles either if your characters are at proper level. The worst trick the monsters in this area have up their sleeves is the Death Sentence attack, which really isn't all that frightening unless you attack very slowly. It's an Enemy Skill, so make sure it gets cast on whoever has the materia.
The next few areas up are a little bit of a maze. Proceed through the open tunnel after those three little caves. You can head left and down to get to the ledge in the first area, where you can pick up Added Effect materia. However, don't run on the brown slicky patch on the way; or you won't be able to stop, and if you hit the wall, you will get seriously injured, Indiana Jones style! Not too badly, but enough so you'll want to heal up.
Head up the right side of the room and then left and go down the steps and go further south to find the Black M-Phone for Cait Sith in the first chest you see in the room. Then double back but don't go back up the steps, instead pass through a tunnel on the right side of the steps. You'll pick up an Ether in the other chest. Now head back up the stairs and go northward. In the next area you'll find five passageways, the far left and right are interconnected and the middle has nothing to explore, thus you are left with two actual choices. The second from the right has a battle with a Stinger, use Frog song on that one, and then press on to find an X-Potion. Head back down and go into the second from left tunnel and you'll have to encounter two more Stingers and then enter the wall on the immediate left after the second web to reach for Turbo Ether. Don't leave this area just yet, but instead, head back to where the second web was and head to the leftmost side and head downward into the "secret tunnel" to the right for a Fairy Ring! Afterwards, head back up and prepare for another gigantic fight.
Eventually, you'll end up in a big cave with a nasty-looking Gi Nattak!
After the fight, you are rewarded with the Wizer staff and be sure to pick up a Gravity materia from the floor. Happy ending: Red XIII finds out that his father was really brave. Time to leave Cosmo Canyon. Red XIII will follow you, and now has a Seraph Comb weapon which you can equip as it's not really that bad. Your Buggy gets repaired by the local mechanic if it broke down; if not, you may have to find the mechanic wandering outside of the buildings in Cosmo Canyon.