For perceptual color difference, there are much better metrics than “distance in linear RGB”. CIE has some implementations of a metric called ΔE*, for instance.

I don't know if they actually do well in dithering, though. My experience with dithering is that it actually works better in gamma space than trying to linearize anything, since the quantization is fundamentally after gamma.