I assume you want to calculate the driving distance from the user's location. So you pick something like 20-50 nearest points (a very cheap and quick operation with a geo-spatial index) and then you will calculate the driving distance to each of them using something like Valhalla, which is much more expensive, but it scales linearly and can be parallelized.
The problem is I have 5MM "users" through several years and I want to compute their distance to a set of points that change through time, so I do care a lot about speed.
Computing the geodesic distances was slow but not that slow because I used a variation of R* with some caching on top, but I still had to compute around 5MM distances or so.
How can computing geodesic distances be slow? Isn't it rather trivial math? I'm pretty sure 5 million of them can be calculated in a few seconds on my laptop. And it can be offloaded to the client.
Whereas route calculation can't be easily offloaded.
So the 100+ million number is irrelevant.