I wrote a bunch of fancy Perl and bash to do video encoding with config files an all, but that's all been replaced with mencoder. These commands assume that the device display is 320x240.
This is what I use almost all of the time. It will scale video down to a max width of 320px, preserving the aspect ratio. For widescreen content, this will result in a letterboxed playback on the device since the display is 4:3
mencoder -vf harddup,scale=-3:240,crop=320:-3 -oac lavc -ovc lavc -lavcopts aglobal=1:vglobal=1:vcodec=mpeg4:vbitrate=300:vmax_b_frames=0:acodec=libfaac:abitrate=128 -of lavf -lavfopts format=mp4 -o OUTPUT.mp4 INPUT.avi
This version will scale a video down to 240px high, and calculate the width to preserve the aspect ratio. It then crops the video to 320x240 from the center. This is a cheap and easy way to view widescreen content with the sides chopped off so it fills the screen of your device. Generally I sneer at the idea of cropping or stretching video, but with a screen so small, it makes sense to do this.
mencoder -vf harddup,scale=-3:240,crop=320:240 -oac lavc -ovc lavc -lavcopts aglobal=1:vglobal=1:vcodec=mpeg4:vbitrate=300:vmax_b_frames=0:acodec=libfaac:abitrate=128 -of lavf -lavfopts format=mp4 -o OUTPUT.mp4 INPUT.avi