Floyd–Steinberg is pretty great when your palette has reasonably-close colors.
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 :)
I do agree it would be nice to extend gimp to do all sorts of fancy dithering, and imagine it's just that nobody has put on the work yet.