Well... there are a couple options for you that I've been thinking on that you may like:
One... You could buy an AppleTV in a couple weeks as soon as they figure out the art of loading Linux on to it. They've already proven they can boot from the USB port and it should have enough power to do media playback to an HD TV. I don't know what the support would be for the remote under linux, but I'm sure you could use my wireless solution for option #2. (read below)
Two... I priced out a computer on Newegg.com for the same purpose. I ended up using a uATX mobo w/ semperon 3000+, 512 RAM, 80GB SATA WD HD, GIGABYTE GV-NX73G128D-RH GeForce 7300GS (w/ no fan), and Bluetooth Adapter for a Nintendo Wii-Mote. What I had priced out was $353.90 not including shipping.
I think option 2 little more beefy than an AppleTV. But the ATV is a little more sexy though. But those are my thoughts.