Are there sorting algorithms that take advantage of a metric space?
For the searching problem (rather than sorting), your idea sounds like interpolation search.  Binary search uses only the binary result of the comparison (less than or not), and runs in $O(\lg n)$ time.  Interpolation search also uses information about how close the values were, and heuristically runs in $O(\lg \lg n)$ time in the average case.  Thus, that's an example where using the extra information can speed up search (at least heuristically).