ffmpegx is pretty good once you figure it out, it's not free but I don't know what the limitations are, I've had it for ages and it still works.
It's amazing how quickly the iPod has changed our needs for videos. Everybody seems to be ditching avi in droves for H.264.