First, I've got to say: Linux doesn't belong anywhere near the headline! This is really nothing to do with Linux!
(Edit: thanks for the update! : )
It seems to me like a NES or perhaps Famicom should be pretty comparable to computers from the 1960's. So, if you stick to OS technology of that era (and that should include Multics and the original Bell Labs' UNIX), you might have a workable plan.
What would be more useful is probably to port an OS kernel people might use on microcontrollers to it, though. I have no real sense of what's out there, but I'd imagine there should be something worthwhile.
Anyway, I think it's just awfully hard to do anything that's general, practical, and useful with even 32 kB of memory. It'd probably always be too much of a toy. The N64 though? Now we're talkin!