As you said, cLinux exists - so if you want Linux on an embedded device you can have it. Just not on an Arduino (or at least not on any models I’ve used).
IIRC, the critical factor was a CPU that was capable of multi-tasking. In the x86 world, that was a 386 or better.
But who knows whether some version of Linux can't be run on an Arduino if that Linux version can be cut down enough?
There were some versions of Linux that used to fit on a couple of floppies, or maybe even just one floppy. Or am I thinking of something similar like QNX?
The Due, for example, has the following specs:
> 96KB SRAM, 512KB flash
Source: https://docs.arduino.cc/hardware/due
(And that’s one of the beefier boards!)
Back in the early 8-bit days, any RAM greater than 64K and disk-based storage more than about 100K was 'looxery,lad!'.
Those machines also famously couldn’t run anything more powerful than CP/M. Let alone something as heavy as Linux.