While I can tell that this code focuses on accuracy, or something like it, it uses float64 throughout, which is very slow.

I wrote a micro-benchmark to demonstrate:

$ go test -bench=.
BenchmarkColourDiffRgb-4                2000000000               0.84 ns/op
BenchmarkColourDiffLab-4                 1000000              1349 ns/op
BenchmarkColourDiffLabNoConversion-4     1000000              1318 ns/op

where ColourDiffRgb is this, ColourDiffLab is this and ColourDiffLabNoConversion is calling DistanceLab() between two colorful.Colors without converting from color.NRGBA.

Perhaps either use some approximations, or do math in either float32, or possibly a fixed-point format.