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.

Not necessarily. I'm working with B&R's range of industrial controllers at the moment, which are Atom processors with a few hundred Mb of RAM and CF cards up to 32Gb, but still running a traditional RTOS with hard timing guarantees. They have built-in web servers and (basic) web browsers...!