I personally like
Handbrake for video conversions. I've had to do a few format conversions for various websites I've managed (including a fairly big job last year of converting a friends website to be compatible with mobile devices), and found that it's by far the easiest to use. I've only used it on Macs, but it's available for Windows, Ubuntu, and Fedora as well.