I once ran an "embedded" Linux on a $10 marvel SOC. It was a pretty vanilla kernel running a basic Debian install. 10MB out of 128MB RAM used most of the time.

Obviously you can go much slimmer, but a $10 board is surprisingly capable.