While chasing down a fairly pedestrian story on Slashdot about building your own LCD picture frame (seems rather obvious, use a box, a VIA motherboard, some minimal carpentry) I did find an interesting link to Mini-Box.Com.
The link was in reference to their small power supplies, but they also sell a cute little embedded PC called the mini-box M100. It’s a mere 20cmx4.4cmx22cm and weighs only 1 kilo. If it had two network ports, it would be idea for an embedded gateway/firewall box, but it also has enough power to do PVR or jukebox functionality well.

Price is around $400, which is high but not insane. I can’t justify gettting one for myself (I have a surplus of computing equipment at the moment), but if you have need of such a thing, you might give it a look.