It is impossible to create a three dimensional color space in which Euclidean distance corresponds directly to perceived color difference. There are dozens of papers on this topic, for anyone who wants some fun evening reading.
On that front, it's amazing to see how much of an effect "switching color spaces" can have on many algorithms.