XBMC runs on Windows, Mac and Linux (although I
hear Boxee is a better choice for Macs). There's even a LiveUSB build for it.
There are a few more options for Linux:
Moovida (used to be known as Elisa) is a slim-but-customisable media center app, and then there's the
various Linux distributions based on MythTV. In terms of ease of setup, I believe XBMC should be the most fuss-free.
Hardware-wise there are a few cheap options available, generally (in no order of merit):
1) Intel dual-core (E7200 and up) with G41/G45 motherboard
2) AMD dual-core (Athlon64 X2 and up) with 780/785G motherboard
3) Intel/AMD dual-core with Geforce integrated-chipset motherboard (last I heard there were lots of driver issues, don't know if those have been resolved yet).
The Intel 4-series chipsets and AMD's 780/785G already support hardware-accelerated decoding (not as good as a discrete graphics solution, but decent enough for an HTPC), and needless to say Nvidia's chipset will definitely support hardware acceleration.
If you intend to watch Bluray discs on the HTPC, there are
a few key issues you should take note of, namely how much support each chipset has for things like 8-channel LPCM and 24p playback. For watching MKVs, I am fairly sure any of the above-mentioned options will suffice (assuming they are properly configured).
I don't have any actual hands-on experience with the above setups, except for the family desktop. It's a Pentium dual-core (E5300) on G41 chipset, plays Bluray 1080p rips fine with Zoomplayer and Microsoft's h264 decoder in Windows 7 beta. A test run with XBMC plays 1080p content smoothly (no doubt with a few framedrops here and there, but decent performance for the price). Based on that I think any mid-range dual-core and up should have no problems even without hardware acceleration.
Another option that is quickly becoming popular is
Nvidia's ION platform. It is simply a Geforce 9400m platform paired with an Atom processor (keep an eye out for the dual-core ones); the CPU performance is weak but when propped up by the 9400m, it actually
manages HD decoding quite decently. Its popularity mainly stems from its low profile (ION boards are mini-ITX form factor, ~7x7 inches or 17x17cm), low power consumption (~30W max) and relatively low cost. You'll have to read up more on this yourself, since I haven't researched into this option in-depth.
Keep in mind that these options are designed toward low budgets (as requested by OP) and efficient power consumption (personal obsession of mine), hence the focus on integrated or cheap graphics hardware. If you have a bit more to spare, I'll let other people discuss the video cards you can buy with that surplus.