Try Mediamonkey if you are on Windows, not sure what formats it supports but it can do it on the fly. As in it will convert them while transferring to your phone so you don't have to keep dupes
I use Ashampoo Movie Shrink & Burn 2 for all my compression and encoding needs.
VERY simple interface, just choose what format you would like the video to be in, how big you want the file to be after its encoded, then hit start. Highly recommended.