The question "Should I introduce this dependency?" really "should the reference object know the nature of this dependency?". Er, only denied.
If your class is FastestPonyFinder, and it needs to be sorted List<Pony>by speed, then I would say that it should know about the comparator. The comparator should compare by speed, sorting the fastest to the list title; no other comparator is suitable for operation. The object must create a comparator, just as it did List.
If your class is BestPonyFinder, then a comparator should probably be introduced into it, because the definition of what constitutes the “best” is separable from the definition of how to find the pony that meets it. This will make your code easier to test and easier to change in the future.