I have run x11 in 16-color and 256-color mode, but it was not fun. The palette would get swapped when changing windows, which was quite disorienting. Hardware that could do 16-bit color was common by the late 90s.
Fun thing - SGI specifically used 256 color mode a lot, to reduce memory usage even if you used 24bit outputs. So long as you used defaults of their Motif fork, everything you didn't specifically request to use more colors would use 256 color visuals which then were composited in hardware.