jamiepda: This has been covered a couple times before on this forum, which is why you aren't seeing many people chime in. I'll try and answer this in hopes that people searching in the future find this post.
Executive summary: The bandwidth between the CPU and LCD controller on the N800 is the absolute limiting factor of what's theoretically possible. IIRC, 640x480@24fps would be close to the theoretical limit of that bandwidth. (See here for more info.) the N810 is almost exactly the same hardware, with the only real internal changes being some more flash memory, miniSD vs 2x SD, and a GPS, so it shares the same limitation.
Now onto, the good news: The LCD controller can do pixel "doubling" with no performance impact (arbitrary scaling, really). If you're going to transcode anyways, xvid/divx video with mp3 audio works great. 400x240 @ 800Kb/s or so is bulletproof. It looks great on the screen and plays flawlessly even with lots of fast motion. The builtin media player is decent and mplayer is available as well thanks to the excellent work of a forum member named Serge. Mplayer supports a couple of formats the builtin player doesn't and vice versa. AFAICT, one of the big things that might affect playback is actually the audio encoding. MP3 decoding usually happens on the DSP on the N800. Even if it's done in user space there are more than one fixed-point, ARM optimized mp3 codecs available. The situation for other codecs varies but I could definitely see AAC decoding taking siginificantly more CPU power. Anyways, that's someplace to start at least. Hopefully I don't have anything too horribly wrong in there. I'm sure someone will correct me if I do.

-John