This may be asking for trouble but, since I'm new here, I can just claim newbie-ness.
I encoded the same clip from Kill Bill in a bunch different qualities and sizes to test the playback quality on my Zaurus. A couple guys around the office have been playing them fine on their PPCs. The samples are at http://www.lilmikey.com/zaurus/video/ and they're all xvid/mp3. The people around here have been using a free program with the generic title "Divx Player" but they should be playable on anything that can handle divx.
I beg ya'll to play nice though. I'd rather not go over my allotted bandwidth and the larger clips are...err... large.