In my own experience playing with dithering, generating a palette is often harder than the dithering itself.

Heckbert's median-cut algorithm usually does a great job. See https://web.cs.wpi.edu/~matt/courses/cs563/talks/color_quant.... There's probably something improved since then, though.

That's cool, and resembles my own approach, which I'll reevaluate and polish now :)

Delighted to help! I've never implemented it myself.