The outlets can be built to share and distribute available power, so the grid connection required is not as huge as you might think. In practice this isn't an issue, as it's unlikely that every outlet will be drawing the maximum current at the same time.
https://www.pluglesspower.com/learn/tesla-model-s-charging-h...
You certainly don't need to run separate circuits over long distances for every individual outlet. You can run one higher-power cable to a hub unit which then breaks out to many (maybe dozens) nearby outlets.
Doesn't this re-introduce the original problem? If less power is available, you have to spend longer charging.
Not a realistic concern, at present, because the chances that a large parking lot will be filled with even 10% EVs is small. At any given time, most stalls will be occupied by fossil cars, cars not needing charging, or will just be empty.
In the future as demand increases, if you start to hit the limit then you can look at upgrading the electrical supply.
Also, let's not forget that these chargers aren't there for everyone to use, but for those who cannot charge at home. For those who can charge at home, that will be a much simpler, cheaper solution.