Here are some good resources on how to get Ubuntu to compress videos for the 5G iPod using ffmpeg:

UPDATE: Upon further review, playback of these files is poor on the iPod. They will play for a few seconds and then stop until you seek a few seconds forward. It appears that a format adjustment is in order. I'll update again as soon as I find a solution.

Installing ffmpeg took a combination of this post and this post, which discusses compiling x264 from source.

As it turned out though, I compressed the video with xvid as discussed here.

Here's a quick script to compress all the .avi files in a directory, naming the output files with a .mov extension tacked on the end. It does check to see if the output file exists, so as you add files to the folder and rerun the script, it won't recompress files.

NOTE: I've also clipped out the relevant sections from the articles and placed them into a collection on Clipmarks.com, a new service I'm trying (although unfortunately they appear in reverse order). It seems like a straightforward and potentially useful service based around a pretty nice Firefox extension.