The performance concern is real but there's another footgun that surprises people in practice: images with large white or transparent backgrounds — product photos on e-commerce sites are the classic case — where the dominant color ends up being white or near-white, which is useless for any branding or UI purpose.

The fix that works best is to either filter out near-white and near-black pixels before the clustering step, or to look at the distribution tail rather than the mode. The most visually interesting color in an image is often not the most frequent one — it's the one that would be chosen as an accent color by a designer. That's a harder problem than it looks because 'visually interesting' is partly about contrast and saturation relative to the rest of the palette.