Personally the one thing I always associate with 256 color games is the dithering patterns. Now historically, they were a result of working within a limited color palette. But there's just something about the grittiness of it that is very pleasing to the eye. Unfortunately a lot of games that claim to have "retro" graphics are missing this aspect, making it look kinda cheap as a result, like they took high-res, high-color graphics and just resized them. Take this as an example:
imgsli.com/MTI2NzQx
With just a couple shaders it looks much more retro-accurate and interesting to me. Unfortunately in motion this shader trick doesn't look that good, but hopefully you get the point.