Everyone seems to assume you need protected mode to run multi-user systems, too.

It wasn't as secure or as easy, but you could certainly do multi-user systems without protected mode and within very small RAM amounts.