I frontier has some great 3D, but a bit lacking in the 'trouser department' when it came to colour (think it was 16 colour, with a seperate 16 colour command panel). Still, at least managed to avoid dithered shades. I remember Braben saying it had a dynamic palette.
What about Gourard shading thomas? how processor intensive is that to calculate? (more or less than texture mapping would you say?)