SUPER is nice for ease of use and presets for common devices. I doubt it will have settings for each specific phone, though. While being easy to use, it doesn't offer as much customizable settings and best converting quality.
H.263/H.264 should be the best video codec if thats supported on the phone.
Well the whole point of codecs are to get the best quality with the lowest size.
There are tons and tons of conversion programs out there though, and they can have some complicated settings for someone looking for top-notch converting quality.
You will probably be happy with something thats just easy to use.
DoubleTwist is suppose to convert media for android phones, though I have no idea if that works on a mac.