Consider natural barriers like rivers too...
If I were to use something like this in the DC area, I'd want to consider that there are only a few Potomac river crossings. Thus a Lat/Long bee-line distance may be quite short, but the actual distance may be much longer due to the necessity of going across a major bridge.
If you were looking for the nearest McDonalds, it wouldn't be an issue. If you were looking for the nearest IKEA, it would be.
There's probably not a simple way around this problem (unless you're tied into MapQuest or something similar), so giving several possible answers and letting the user choose is probably the most reasonable approach.
Cheers,
Scott.