Benchmarking done, but until I post a full analysis, I've found a "silver bullet".

This was on a single-pass encoded DivX, 352x240 @ 25fps.

I've found that if you encoded them with any video bitrate (well, I tested up to 600kbps) but keep the audio bitrate at 96kbps, and play it back on mplayer using "-vo x11 -ao gst -ac dspmp3 -cache 800", you get minimal frame drop.

With the "-noframedrop" flag set, a 60-second video took between 60.0 and 60.8 seconds to play, so I guess specifying "-framedrop" to handle the minimal amount of dropped frames would give you a VERY smooth ride.

More later once I've fully analyzed the results.