For full lists of every character's Weapons, see here: Weapons Lists
Ultimate Weapons have 8 linked Materia slots, no Materia Growth, and the damage they do is dependent upon a wildcard factor. Aeris has no ultimate Weapon (although some argue the case for either the Princess Guard or the Umbrella).
In most cases, each character's ultimate Weapon is also their best Weapon. However, this isn't true of Tifa and the Premium Heart. Damage caused by the Premium Heart drops to very low levels when Tifa's Limit Bar is empty or nearly empty.
As such, I recommend using Tifa's God's Hand Weapon instead. As the name would suggest, it's actually a very powerful Weapon. For a full list of Tifa's Weapons, click here.
Barret's Missing Score can get ridiculously powerful by putting enough high AP Materia into it. In fact, with 8 mastered Knights of Round in, it will instantly kill ANY enemy in the game. Vincent's Death Penalty can take a hell of a lot of grinding to power up as its power depends on the number of enemies Vincent has killed, but it is also capable of instantly killing any enemy once you max it out. For details on this, check out the 'Foolproof instant kill' video on my YouTube page. All credit to whoever first discovered this - it certainly wasn't me.
For Cloud and Cait Sith, you may want to consider giving them a Master Command-HP Absorb materia pairing. Likewise for Red XIII and Cid, you may want to use Master Command-MP Absorb. This will allow these characters to keep either their HP or their MP topped up with their default Attack, which ensures their ultimate Weapons stay powerful. For more on this, please see my Advanced Materia page.
Yuffie's Conformer has damage that conforms according the power of your enemy, so it's a particularly good one.