If you've got the Airship sign up Wakka. Rin is also available on the airship as is brother.

Theres a good defender you can pick up in the shop on the Mi'ihen high road. Also as already mentioned theres Kyou near Djose Temple.

Once you have a team that can win games just try to sign up players who don't have there contract re-newed. The Al-Bhed tend to be the best ones.