Super cheap? Raspberry Pi in the $35-50 range, depending on what parts you already have. Surprisingly awesome for the price. Really hard to go wrong with a Pi, since you can use it as a ton of other things if it doesn't meet your HTPC needs.
$50-ish range (give or take $20): Almost anything that isn't Allwinner A10-based (the processor inside), and has a wired ethernet port (most android boxes have crappy internal wifi, even if you have good range). Beware, you get what you pay for, and the Pi might actually be a better deal due to nice quality and very strong community/tech support.
$100-ish range: OUYA, that quadcore Mini X something, various Google TV devices. There's various threads floating around about what is the current "best" Android-based box, and YMMV.
$150-$200 (best bang-for-your-buck for power/price starts here): Something Celeron-based, like a mini PC such as the NUC (Get a "barebones" one and add ram and a USB drive to boot from +
OpenELEC (wiki)), or piece it together from newegg, etc.
$200+, see
http://forum.xbmc.org/showthread.php?tid=94199 for some pretty good advice on pre-built/easy to configure set-ups and what they give you for your money.
(also, this is my 15,000th post. I need to get out more...)
