Handbrake? I'm pretty sure it's for every platform (PC, Mac, Linux)
Convert to .MP4. You can pretty much choose the bitrate and resolution to your preference.
When I convert my HD movies, I usually use 854x480 (full resolution of the phone) at 800-1000kbps. That results in an incredible picture.