MPEG4 video at 30fps or less around 1000Kbps, at a resolution no greater than 400x240 (fit whichever dimension hits the edge first depending on aspect ratio) with MP3 audio—perfect playback, every time.

This is a copy and paste form a post by GeneralAntillies, but it's pretty much what I've been using for the last year on the N800. Works well for me.