You could try one of the Windows-based utilities for creating movies for Sony's PSP... they both pretty much play the same format of MP4 files (320 x 240).
Its not free but I have had the best luck using Nero Recode. It takes me about 26 minutes per video to encode. I already have the first season of smallville on my iPod. There is a tutorial at http://arstechnica.com/guides/tweaks/ipod-video.ars/5