How to discern which color is "lower" and/or "higher" in CIE-L*a*b* colorspace for ordered dithering?

This paper describes the problem very close to your question, and then proceeds to provide an algorithm to solve it:

http://ira.lib.polyu.edu.hk/bitstream/10397/1494/1/A%20multiscale%20color%20error_05.pdf

Hopefully this helps.