Media Coder is an open source video transcoding utility. It supports a large number of formats, and plenty of advanced options for tweaking all of the encoder settings. Fortunately, an extension that is included in the typical install makes it all very easy to use with various presets for small and large video outputs for various formats. It also has presets for various media players such as an Ipod.
I’ve have yet to find a format that it can’t work with, and have had great success creating videos for use on my 5th generation Ipod and my Motorola E815m.