What is a good color similarity metric?
If complex metric is acceptable I would suggest to look at perceptual based approach described here. The metric is designed to pick perceptual difference of two images. There are two main tests for that : luminance based and color based. First one allows to answer the question how important luminance change is by estimating a non uniform threshold factor based on sensitivity to contrast changes depending on spatial frequencies of the image. The second one is based on euclidean distance in CIE LAB color space, but slightly modified to make color difference less important when luminance is in mesopic and scotopic ranges. A list of papers related to that metric can be found here.