The "made for PDA" (not the iPod or PSP ones) movies on this site (http://www.publicdomaintorrents.com/index.html) play rather well. They're 320 wide (usually 240 high, depending on the aspect ratio), 23 fps and around 250 kbps (I keep getting different numbers from different encoders, so there...).

Strangely, videos play a lot better on my N800 through Canola than through the regular video player (I can't figure out why, as Canola is supposed to be just a frontend). Mplayer is really awful on my system; tears like mad.