At 60mm x 60mm x 13mm the MiniX TV Box H24 is the cutest set-top box ever. Powered by an Allwinner A10 CPU (1.2ghz ARM Cortex A8 and MALI400 GPU) it's running Android 4.0 but is highly hackable.
Liliputing notes that it's already Ubuntu, Fedora, and Puppy Linux compatible.
✓ 512MB DDR 3
✓ 4GB Nand Flash
✓ 2 X full size USB 2.0 host
✓ 1 X MicroSD slot
✓ 1 X HDMI
✓ Wi-Fi 802.11b/g/n
✓ External 5V power adapter
✓
$99