EDIT: Link to zipfile. Contains GPL (GIMP/Inkscape/Mypaint/etc), PNG, and SOC(OpenOffice/LibreOffice) versions of each palette.
Also an Imgur gallery for quick preview
First serious help! But please force both pure white and black and reduce potential of NES palette problem (lack of good saturated red/yellow/green/cyan/blue/magenta).
That's actually a problem inherent to both K-means and median-cut reduction methods, which the added contrast was intended to counteract.
However, if you want exact black, you can just replace the darkest color with black, same as I did with white.
I didn't really care about -extremely- saturated colors when making these, though.
For 'general purpose' keep in mind text console palettes, black/white monochrome, games, etc.
But... Have you tried your palettes?
Of course I have tried my palettes, on a wide range of stuff from pixel art to photos. That's how I can say it's the best I've seen (reasonably accurate and reasonably legible, over a wide range of content)
Is the palette below good enough?
This is a subset of 16-16-16 level RGB where values are from 0 to 15.
No, it's not good enough then, since the whole 16-16-16 RGB cube (4096 colors) is not good enough.
All RGB colorcubes that aren't huge( 64x64x64) have the same problem -- too many saturated colors, lack of good pastels. Which are exactly the problems shown in your palette.
(this is putting aside the problem that 256 colors, no matter how 'optimally chosen', can never approach the quality of a palette chosen specifically for the work in question. An optimally chosen 4096-color palette is about the minimum size of palette I could believe was generally high quality enough to use on everything)
Surt posted a colorcube exploring tool
http://img.uninhabitant.com/colourcube.html a while ago in the Off-Topic Thread, which includes the kind of options you are exploring here, and many others..
I don't think you need so many pinks and purples. There's no good browns in there either. I think the cyan ramp should be fine and I can probably work with the green ramp. I seem to lack saturation in the oranges.
)
If this is addressed at my palette (of which there are several variants), I agree completely. Those are pretty much the exact problems that I found. To me, we have these two approaches: colorcube generation, and reduction of colors from a set of 'representative' colors. If we could figure out how to combine the strengths of
both, the result would probably be more suitable.
IIRC you can specify weights as an input to k-means clustering, which I think would work to emphasize whatever subset you think is important.
I also made a hand-optimized palette for the OHRRPGCE's new default, in 2008. The users abuse it just as badly as the old default

. But anyway here it is:


Each 'row' is 15 colors, which means I needed to add 14 duplicate colors to the end to make it fit in the image; that's why it's 15x18 in size.
I don't expect Piotr would think this one is relevant to his project, since it really doesn't care about completely saturated colors at all (in fact, it minimizes them in order to maximize points where ramps can cross over.)