I hate Locke, there are no items he can get by stealing, that are not possible to get another way. I'd go with edgar, his chainsaw always did 9999 for me. In fact, I never used that genjiglove/offering trick, I just used the characters special abilities.

Gogo/Edgar/Sabin/Cyan was my party, and they were unbeatable... the only spell I really used was quick... final boss all forms didn't get hit...

But yeah, I never liked Locke, not even a little, my two favorites were Cyan and Sabin, but that's just me... and just give your offering trick to one of the girls if you want it, it's better than magic anyways...

So in your case, I'd say Terra/Celes(cause you want those two) and Sabin/Cyan... but that's just me...

THE JACKEL