My P3-866 with a GeForce 4MX can handle most video formats and (scale) output them at 1080p - anything that it can offload onto the graphics card. I use VLC for video playback.
It didn't have a hope of handling the amount of videos it can handle now before I put that graphics card in. Its hardware acceleration support for video formats isn't universal but it handles about 95% of the videos I've played on it.
I'm retiring that computer shortly, sadly (IMO). It's nice to see a bit of kit that is still completely reliable and yet pretty damn old, but I rely on it too much to keep trusting to luck.
There are AGP cards with DVI ports, and you can get a DVI -> HDMI adapter from there. Plug the computer's audio out to the television's auxilliary audio in and you're set (I think). My server is hooked up by VGA to my TV, with an audio connector in the way I just described.