Here's what I put together, and it should be around $800
Shuttle SV24
Celeron 766
256MB PC133
Pioneer 106S (slot load dvd drive)
Western Digital 60GB 7200rpm
ATI All-In-Wonder PCI 16MB
19" monitor
Wireless keyboard/trackball combo
With this setup, I can watch TV, record shows, play Playstation through it, games, movies, etc. I'm sure now you can buy better components, but with what I have, I've been more than pleased. It's been a stable setup, and it's nice and small.
If I were to suggest changes to this, I would say a faster processor (one preferably running at 133mhz FSB) would be a huge help in recording TV shows. Small cases like this one are also available with an AGP slot, but cost more.
As far as software, I mainly use Windows XP, Winamp, Power DVD (or WMP works fine too), and the proprietary software that comes with the ATI card, but stay FAR away from ATI's multimedia and DVD player.
Hope that helps!
EDIT: This is what I put together about a year ago for myself, and it was about $800, so I'm sure you can get much more now for the same price.