Pixel artists have really, really explored that problem space. You might want to check out the palettes on lospec, and the discussions about these things on pix

Pixel artists have really, really explored that problem space. You might want to check out the palettes on lospec, and the discussions about these things on pixeljoint. I'm not deep into colour theory myself, but I get awed by the diagrams Dawnbringer's palette analyser tool produces, let alone the things pixel artists do to highlight the opportunities and limitations in palette choice.