This is the smallest Linux I know: **broken link removed**
EDIT: Sorry, that linux is not particularly small, but it runs on minimum resources. The smalles Linux I've seen fits on 16 megabytes of flash and that system has 32 megabytes of SDRAM. **broken link removed**
an LPC1788 is $14 and has CAN, EBI/EMI, Ethernet, I²C, Microwire, MMC, SPI, SSI, SSP, UART/USART, USB OTG, Brown-out Detect/Reset, DMA, I²S, LCD, Motor Control PWM, POR, PWM, WDT.
So you have your choice of USB or SD for mass storage, ethernet on chip, kernel on chip (512K FLASH, 96K RAM on chip), up to 1G of SDRAM (32bit data, 80MHz), and an LCD controller all on chip