Red XIII's Ultimate Weapon

Red XIII's best weapon is called Limited Moon. After you have taken Bugenhagen to the Forgotten City and defeated Hojo in Midgar, return to Cosmo Canyon with Red XIII in your party. Go up to Bugenhagen's house, where you'll find the old man in pretty bad shape. As a dying gift to his grandson, he gives you Limited Moon.

Red XIII's Level 4 Limit Break

Red XIII's Level 4 Limit Break is called Cosmo Memory. When you go into the Shinra Mansion in Nibelheim, go up the staircase and to the left. There you'll find a room with a safe. You'll need to open the safe, but be warned: if you go past any of the numbers, it won't work. Use circle to enter the numbers. The combination is right 36, left 10, right 59, right 97. After opening the safe, you have to fight a boss called Lost Number. Beat him to recieve Cosmo Memory.