I'd choose Tifa over the others because she has more involvement with the plot, but Cid is better in battle.

As for the Sahagins, I believe I know what the problem is. Usually they take normal damage from physical attacks and 1 damage from magical attacks, but occasionally they switch this over and take only 1 damage from physical attacks. When this happens just hit them with a magic spell.