What is the fastest way to compare two lists of doubles with some tolerance?

You could try to create a custom made extension method to check a number in a list with tolerance:

public static class Utility
{
   public static bool HasApproachingValue(this double[] array, double value, double precision) {
      bool result = false;
      for (int i = 0; i < array.Length; i++) {
         if (Math.Abs(array[i] - value) < precision) {
            result = true;
            break;
         }
      }
      return result;
   }
}

Which you could use like that:

double[] firstList;
double[] secondList; // These list should be initialized with values
double precision = 0.005d;
for (int i = 0; i < firstList.Length; i++) {
   if (secondList.HasApproachingValue(firstList[i], precision)) {
      // Here's a match
      break;
   }
}

The worst-case scenario will be when there is no match, as there will be (firstList.Length * secondList.Length) occurrences.
Hope this helps.