You can't really see any quality benefit with high quality settings on such a small screen. For example over about 400k video bitrate there is no visible change, only a bigger file size. Even making AVC for use in original firmware won't give you a file that also looks high quality on a normal laptop/PC/TV screen.
When encoding for devices which can't scale or expand the picture according to aspect ratio it is much simpler and easier to use Mencoder than ffmpeg. I wrote a script to use in Debian that will work equally well in any Linux or BSD or OS X or similar, so long as you have bash shell, MPlayer and Mencoder. If you are using Windows bits of it might be useful in configuring a Mencoder GUI.
Brief summary from the script:
# This script encodes video for playback on Rockboxed players. It
# automatically detects and applies good crop values. It automatically
# scales the video to a suitable size. It detects the audio type in the
# source video and transcodes it only if necessary. There are options
# to make sample encodes (tests), to specify output directory, to
# disable autocropping and to choose higher quality encoding.
# Run the script with no options or arguments for some short
# instructions & read the comments at the end of the script.
The script can be found at
http://pastebin.com/Vp3fTdBuI have to admit that I rarely use it because the Fuze+ and other Rockboxed players don't hold much appeal to me as video players as I have a 4.3" screen Android tablet for this that can play 720p.