After much pain and research with ffmpeg and mencoder, I stumbled upon MMC – Mobile Media Converter. It seems to be a front end to FFMPEG, but works seamlessly. It has quality presets, as well as customizable transcoding quality settings, for those who don’t want to lose their framerates.
If you’re looking to convert your videos from .avi or .mpeg format to the highly efficient .3gp format (natively supported by the Google Android OS, running on phones such as T-Mobile’s G1), then look no further than this application. The application runs on Windows & Linux!
Click here for their site, the links to the application are at the bottom of the page.