I personally think other posters were being too optimistic. I think you'll be disappointed with any video not transcoded to 400x240 (for widescreen) or 320x240 (for 4:3).

I watch a lot of video on my N800. Video was one of the primary reasons I bought it. I am very pleased with the quality of transcoded video (I usually transcode to One-pass XviD, 550-800kbps, cropped and resized to 400x240).

I am not pleased with the fact that I have to transcode the video in the first place, but I believe that the N800 has a bigger screen and plays video as well or better than any multi-function device at its price point*. From what I hear, future Nokia IT devices will fix the current bottleneck (the LCD controller) that forces us to transcode video.

The other thing I would recommend with video on the N800 is breaking long videos into smaller chunks, unless you know you can watch the whole movie in one sitting. It isn't very fun holding down the FF button through 4/5ths of a two hour movie to get back to where you were when you had to stop.

* I have seen a portable DVD player that has a bigger screen and can supposedly play DivX for under $200, but I haven't tried it, mainly because I don't just want to watch video. The N800 is also a very good e-book reader, web browser, internet radio receiver, photo viewer, instant message client, and Skype client.