The best weapons in the game, and thus for this battle, are the Ultimate Weapons listed below:
Cloud: Ultima Weapon - To get this you need to defeat the Ultimate Weapon. It is the dragon-like creature flying around the sky. If you ram the highwind into him you will have a battle before he runs away. Repeat this process until he rests over Cosmo Canyon and then you will have a final battle with him. He drops the Ultima Weapon as your reward. It's worth noting that the Ultima Weapon scales with Cloud's health. Formula:
Power = [(3 * AttackPower * Cloud'sHP) / Cloud'sMaxHP] + 1
Cid: Venus Gospel - Obtained in Rocket Town after the Rocket launch. The man that used to stare at the rocket will give you this if you speak to him 3 times. Conversely to Cloud, the Venus Gospel scales with Cid's MP. Here's a nifty formula to work it out:
Power = [(3 * Power * Cid'sMP) / Cid'sMaxMP] + 1
Red XIII: Limited Moon - Bugenhagen will give you this before you take off to drop in on Midgar. But you can get this any time in Disc 3 otherwise. Like Cid, it scales with Red's MP and the formula is the same.
For other people's reference:
Barret: Missing Score - You can get this right at the end of Disc 2 when you parachute into Midgar. This is a missable item so make sure you get it. It's in the Sister Ray stairs and Barret must be in the party for you to be able to get it. This weapon scales with Barret's AP.
Power = [Power * [Total AP on Weapon / 10000] / 16] + 1
Tifa: Premium Heart - Obtainable in Disc 3, to get this you have to go to Bone Village and dig up around the same area you find the Earth Harp. You will find a
Key to Sector 5, from here go to the Wall Market and in the shop in the middle (the one that shot at you when you pressed buttons). You'll find the Premium Heart here. Tifa's weapon scales with the amount of her Limit Level Gauge that is filled, coupled with her Limit Level. Interesting note: Once you get the key, you can go to the church you will see Aeris' ghost.
Power = [Power * [Tifa's Limit Level * Limit Bar Units / 16] / 16] + 1
Aeris: Princess Guard - It's located in room 4 when you use the clock system just before the fight with the Demon Wall. The attack power doubles if one ally is dead, and triples if two allies are dead. Note: This isn't actually her most powerful weapon (unless there are dead allies). It is in fact the Umbrella, which you can win in the speed square by getting over 5000 at the mini game.
Damage = Damage * (1 + Number of Allies in Death Status)
Cait Sith: Marvellous Cheer - When in the Shinra Building at the end of Disc 2. Search the lockers on the 64th floor and you will find this weapon. Like Cloud's weapon, it scales with the character's health.
Yuffie: Conformer - This inside the Sunken Gelnika. Which you can find by using the submarine, submerging and its kind of hidden around a blind spot. Yuffie's power scales with the level of the enemy, but sadly, I can nay find a formula to illustrate this.
Vincent: Death Penalty - Found in the Waterfall cave. Once again, use the submarine and submerge, you can find a tunnel and if you go through that and rise, you will be by a waterfall. You can dock and then walk into the waterfall. Here you will find Lucretia where you will learn some interesting things about Vincent. Have 10 fights after this and then return, you will find the Death Penalty where Lucretia once was.
Power = [Power * [Vincent's Kills / 128] / 16] + 10
Vincent's weapon and also Barret's weapon are subject to the
Overflow glitch. This is pretty handy because it just instantly kills enemies because of the way the game handles exceptions. With Vincent, killing 65,535 enemies (must be killed by Vincent), will cause the bug to occur and you can freely one shot kill enemies for the rest of the game. Or, with Barret, just equip a mastered Knights of a Round materia to a weapon slot and it will cause the same overflow.