I encode videos for my 3100 using Virtualdub - Xvid codec, 600kbps, MP3 audio at 128kbps/48000 khz
In testing I did a while back, the 48000 khz was important - playing video with 48000 khz sound was much better than 44000 or any divider thereof.
THe resolution I use is 320x240, 30fps, which is *perfectly* smooth on my non-overclocked Z. I've tried other options, including pre-rotated 640x480 and got good results, but the 320x240 videos play just as well on the Z as they do on my computer.
Visually, I find dropped frames or hitches in playback very annoying, and I don't want to overclock, so I stick with the smaller resolution. ALso, ripping DVDs is faster (1.75x real time) vs ripping at 640x480 (~1x real time).