Something I think about sometimes is how it's usually more important to maintain shape rather than color. For example, in the first 2 images on the page, quantizing the pink hearts results in some pink, white, and grey. An error diffusion alg will result in pink speckled with white and grey, whereas it might be preferable to have a solid pink that's slightly off color but has no speckles.

Are there existing techniques that do this sort of thing? I'm imagining something like doing a median filter on the image, run clustering on the pixels in the colorspace, and then shift/smudge clusters towards "convenient" points in the colorspace, e.g. the N points of the quantized palette and the N^2 points halfway between each pair. Then a partial-error-diffusion alg like atkinson smooths out the final result.