There are quite a few GUIs for FFmpeg out there, but I've found Sinthgunt to be the easiest to use - it requires just 3 clicks to convert a video: select the video, select the preset to which you want to convert to, and click "Convert".
Futher more, Sinthgunt comes with over 100 presets for various devices such as iPod, Blackberry, Android and many more. And unlike most applications of this kind, Sinthgunt detects the formats your FFmpeg version can convert, and only displays those (the default ffmpeg can't convert to some formats - see this post (you need to install libavcodec-extra-52) for enabling more formats).
Sinthgunt can preview the files too and it can download a video from YouTube, Metacafe, Google Video, Photobucket and Yahoo! Video and then convert it, so you don't have to do all this manually, thus saving an extra step.
Download Sinthgunt (includes .rpm and .deb precompiled packages)