I was on linux as my main driver in the early 2000s an we did watch movies back then, even DVDs. Of course, the formats where not HD and it was DivX or DVD ISOs. I remember running Gentoo and optimizing build flags for mplayer to get it working, at a time I had a 500Mhz Pentium III, later 850Mhz. And I also remember having to tweak the mplayer output driver params to get a good and smooth playback, but it was possible (mplayer -vo xv for Xvideo support). IIRC I got DVD .iso playback to run even on the framebuffer without X running at all (mplayer -vo fb). Also the "-framedrop" flag came in handy (you can do away with a bit less than 25fps when under load). Also, definitely you would need compile-time support for SSE/SSE2 in the CPU. I am not even sure I ever had a GPU that had video decoding support.