I would do it in RGB space. Run kmeans to get a set of Voronoi cell centroids, 5-6 should be good. Then take the Delaunay triangulation of that and pick a color midpoint between Voronoi neighbors that maximizes the distance sum from all the Voronoi generator points.
