As much as you can afford, though I appreciate that isn't a helpful comment, it's a fair one.
Video decoding does take a reasonable CPU hit. As a general guide, you could take a look at the
mini-itx specifications, those machines tend to be used as video players in peoples livings rooms because they look nice. You could put one together though you certainly would be playing for looks and size
As a vague guide (though don't quote me on this), I'd say something of around 600 Mhz with 256 RAM should play fairly well. As for TV out, I believe (and again don't quote me) the ATI 7500s offered excellant TV out options at a time when nvidia had only just worked out what TV out was. Those cards can be picked up pretty cheap.
As for distro...well I'd always suggest slackware, but almost any would do, there are some distros geared towards media playing, I can't name any off hand but google will help. But as I've said, what I've recommended shouldn't be taken as gospel, other forum members will have other suggestions,
Good luck!
Steve