I really like the low-color but higher-resolution style, like Eigen does in Pioneers.
I did a Gameboy-palette game ("Les blocs de l'est"/"Eastern Blocs") but with an 800x600 resolution, and it was definitely the most fun I've had pixeling, because the greater resolution gives some more room to play with texture as a substitute for color. Some of the little textural details (like that the background is supposed to be a pixelated Gameboy display seen from within, and that the buildings are meant to be stage sets) wouldn't have been possible in the lower resolution.
I think it would be interesting, if your Mars changes over the course of the game, to subtly shift the palette as well. (For example if it's a terraforming story, to slowly shift the middle colors to blues and greens. Or even locally, like a "moisture shader" that takes the ambient humidity within a several-tile radius and reflects that in the palette used.