I was getting the same problem on my iPhone 6, and it was driving me insane. I think it started with the update to iOS 10 because I don't ever remember encountering it before then. The issue, apparently, is not about allowing Safari to access your location in your iOS settings preferences. I allow Safari Websites to access my location "While Using the App" in my Location Services settings in the Privacy tab. But I only get the request to access my location from Google when I conduct a search on my iPhone with Safari.
Instead, it appears to be a Google issue (unsurprisingly). I found one solution on, of all places, Windows Clan. I tried the solution in this article a few times, and it seems to be working so far.
Alas, when it comes to all issues related to MS Windows and Google, it's not entirely clear in the article how to get to the solution, which, as the article states, is to tap on "Use precise location" at the bottom of the page on Safari.
To find it, I typed in "google" in the Safari search bar. Google's home search page appeared in Safari, and at the bottom of that page, I found the option to "Use precise location." When you tap on that, Google will, of course, ask if you want to download the Google Search App (which I've done in the past, but I got sick of the saga you must endure to erase your search history and set any reasonable privacy settings).
You'll also see the option to sign into your Google account and "Settings" for your searches. For a longer and more tortured explanation from Google itself on this entire drama, tap on "Learn more" after you select "Use precise location."
On your Macs, you can stop the requests by going to Safari's Preferences > Website use of location services > Select "Deny without prompting." I've never had any trouble finding the location of anything via a search using Google (or any other website) by using this option on macOS.