One approach I've been thinking about in the past (at least as a rough concept) is for the back-end to round both users' location to an "area" (probably city level or similar), then compute the distance between the centroids of those areas. That way moving around your own city wouldn't change the returned distance, nor would the other person's moving around their own city. Even spoofing API requests wouldn't help much, as you'd only be able to triangulate which particular area centroid the distance is being measured to, and that is probably something the user is already disclosing on their profile anyway.

This could even be done in a relatively private way by only reporting the area level location to the server (not that I imagine many services would want to give up valuable raw location data!), as the server wouldn't need anything more granular.

Obviously there's challenges in more rural areas where population and premises density are lower - how big is the "area" in that case, and is the distance reported that meaningful in these situations?

The way tinder dealt with it, as I understand, is by dividing the world into a coarse grid. Users were placed in the grid, then distances calculated from the centers of the grid squares. Basically rounding of position, not rounding of distance. They tried rounding distance (calculated from exact positions) but one can exploit that by exploring for the boundary where the distance changes from one integer to another.

Round it to a given precision and maybe fuzz it?