I sympathize with your quest. I've spend a good deal of time trying to locate small boards for a CE project my company's doing. No fun. I've gotten in a few development kits (quarter VGA, OS already loaded, touchscreen & various needed bits all in a box). They've been about $1500 each.

The boards I'm looking at are about $350-$450 in single piece quantity, but the processors (300Mhz Geode & 400 Mhz XScale ARM) are too slow for what you want to do (to the best of my knowledge) w/o a separate decoder board.

You might take a look over at PC104.org, there's a good number of companies that are making small form factor stuff linked from that site.

'Luck!

-Zeke