I have always had an artistic penchant for high contrast small palettes. The best way of generating high contrast palettes with equally spaced colours is to chop up the colour cube in a uniform fashion. The default mtPaint palette does this with the first 8 colours which are the 8 corners of the RGB colour cube.
These 8 colours are formed in the 3 RGB dimensions by 2 divisions (i.e. 2x2x2). However a 256 colour palette is large enough to house several other palettes:
3x3x3 27 colour palette
4x4x4 64 colour palette
5x5x5 125 colour palette
6x6x6 216 colour palette
If you are a C language programmer you might be interested in trying out the program I wrote to generate these palettes and images:
pal3456-0.2.zip source code
I have used my own libmtpixel library to make palette and image creation possible with just a few lines of C code.