Head west across the little river, and you'll soon enter the Cosmo Area. On your way you might catch up with the intensely annoying little frog creatures called Touch Me's, which you can learn the Enemy Skill Frog Song from. Eventually, you'll come across a little city in the mountains. If you try to go past it, your buggy will break down, so you really have no choice except to visit the town, which as you'll soon find out, is Cosmo Canyon. This place is the hometown of Red XIII, or as he's known here, Nanaki. Follow Red up the stairs, and take some time out to check out the Weapons Shop. You may want to buy the more powerful weapons here, but if you're trying to grow your materia, you'll probably want to keep using those double-AP weapons you've already obtained (you'll be getting a new set of them soon enough, btw). Don't spend all that money in one place, though. Upstairs at the Materia Shop, you can get the very handy HP and MP Plus Materias! Buy both in quantity. Talk to the locals, too. Finally, you'll have to go up to the top of the place and meet Red XIII's grandfather, Bugenhagen. Gather up your friends, go back and visit the planetarium, then go back downstairs. On the way, don't forget to seek out out the Fourth and Fifth Turtle's Paradise posters here, one in the Weapon Shop, and another on the second floor of the Inn/Tavern.
Talk to everyone around the Cosmo Candle, saving Red XIII for last. After a little bit of conversation, Bugenhagen will come down and take you to the Cave of the Gi, a rather unpleasant place full of ghosts. These ghosts, though, will teach you the Enemy Skill Death Sentence, and aren't too hard to kill. The first part of the cave can be figured out by flipping the switches in the little caves. There is only one that opens the door to the north. It's the one that's one the other side of the first cave you see. The others all have battles inside them. After you find it, head north to a small maze. First of all, head north and go left at the first place possible. At the end of the line there is an oil slick. If you run on it it, you will slide into some spikes on the wall, hurting everyone. However, if you calmly walk along the bottom of the slick, you won't get hurt, and you'll gain access to the southern door. This leads to the rather cool Added Effect materia. If you want to usey now, link it with Choco/Mog or Mystify on your weapon.
Go back up, walk past the oil again, get the rest of the treasures, and continue north. This next maze is a little more confusing, with treasure chests that look impossible to get. The chest in the bottom center can be found by taking the cave leading to the lower left corner of the map, and then going right through the secret tunnel. The chest in the upper left is found by going through the hidden tunnel just behind the large rock to the right. To get to some of these, you'll have to fight a couple Spiders. These can be tough, but if you have Aqualung, it's really simple. Just cast Aqualung once. If that doesn't kill it, a few normal attacks will.
When you're ready, head north to face Gi Nanataku, a relatively tough boss. There's a trick you can use to kill him instantly, though--just throw an X-Potion at him. I'm not making this up! It kills him instantly (he is undead, after all). But if you'd rather go for the challenge, and it is quite a challange, don't use Fire magic. Cure magic also hurts him. When all is said and done, you'll finally find out the truth about what happened to Red's Father, who will give Red the Seraph Comb, a relativly powerful weapon. Now its back to Cosmo Canyon. Your buggy will be fixed, so whenever you feel ready, head north to Nibelheim.