The common way of evaluating a similarity measure seems to be by using the similarity for a particular task, e.g. information retrieval or kNN classification, and then computing precision$@k$ or the area under the roc curve (ROC AUC).
There is also some literature on calibrating such scores. One should however note that a well calibrated score is not necessarily better; for example a weather prediction that constantly gives the year average as chance of rain is well calibrated, will actually be correct quite often, but is not very useful on a particular day (only in the year average).
In my opinion, there is nothing wrong with evaluating a similarity/distance measure for a single, particular task. There are tons of examples for such measures that - just like feature extraction - work well for one task, but not for another. Dynamic time warping distance, for example, just fails badly when you look at sine curves of different frequencies.
Have a look at for example:
Houle, Kriegel, Kröger, Schubert, Zimek
"Can Shared-Neighbor Distances Defeat the Curse of Dimensionality?" Scientific and Statistical Database Management SSDBM 2010.
Bernecker, Houle, Kriegel, Kröger, Renz, Schubert, Zimek
"Quality of Similarity Rankings in Time Series". Advances in Spatial and Temporal Databases SSTD 2011.
This pair of publications seem to do a similar task as you are doing: evaluating whether or not shared-neighbor similarities improve over existing distance measures. IIRC correctly, they also look at the contrast provided by the distance measures, but I'm not sure if they measured this contrast numerically.
If you cannot select the treshold yet, a classic ROC curve might do the trick for you. The area under the ROC curve gives you a good estimation of how well a treshold can work. There is a probabilistic interpretation of ROC curves that is as follows: taken two examples, one positive and one negative: the AUC value is the likelyhood that the two examples will be ranked in the correct order. An AUC of 100% means that they are always right; a value of 0% is they are always wrong, and 50% is the outcome of a randomized ranking. (I do however not have a reference or proof for this interpretation, and it might be numerically off. I do remember having read this somewhere, though, that the ROC AUC equals this statistic)
On the other hand, the ROC AUC does not take the actual values into account, only the ranking. So it does not tell you whether or not it is easy to select the threshold. The publications by Houle et al. above had some pretty nice histogram plots for this, where you could visually tell that for the SNN distances they could just choose 0.5 as threshold, while for other distances there was just no working threshold at all (and the distances were numerically essentially unbounded, while SNN was 0 to 1)
