Hmm with respect to needing to transcode, iliaden found that you can use mplayer's built in options to playback un-optomized files very nicely:

I bundled this into a shell script that attempts to auto-determine the best settings and calls mplayer with those settings for optomized or unoptomized content.

Mopt.tar

download, then untar and chmod with
tar -xzvPf Mopt.tar
cd /usr/bin/
chmod +x mplayer-opt

you can then invoke it on any movie file that mplayer supports by typing
mplayer-opt <filename>

Hope this helps someone, for me it's enabled to me to play full DVD rips (AVI with mpeg2 and mp3) with no lag, playback is smooth and even fast action scenes (as noted by iliaden) render nicely

I'm actually very satisfied with my N810 as a portable movie player
Also, with respect to the streaming thing I've been able to play video streams of The Office on my N810 with no stuttering or lag with a decent internet connection. Also, for me at least, youtube videos play with no lag or hangs. (I'm aware that this might be a processor speed issue, 330mhz vs 400 mhz but upgrading the N800 to OS2008 would improve this)