I also have that problem with FP3 - my PC is connected to my phone’s hotspot, but “no internet”. I found this post, which points to a solution, though one that seems to require a bit of time to implement - Hotspot but no internet on Vodafone UK (pay monthly)
The Android Studio Setup Wizard “Downloading Components” prompt also showed the location of the “sdk\platform-tools folder inside the Android development kit folder”: “C:\Users<username>\AppData\Local\Android\Sdk\platform-tools” in my case (Windows 10 Home).
When using the shell, first time around I wasn’t aware that I had to confirm something on the phone – the error message I got said “Otherwise check for a confirmation dialog on your device” and indeed this confirmation dialog turned out to be there (i.e., on the FP3).
Also, I assumed that “Hook up your phone to the computer” as in the cited post meant ‘try and connect to PC from phone using hotspot functionality’, and that “$ exit” meant “quit[ting] the android development kit” and indeed this seemed to work.
As another note, at some point I thought that the problem I encountered might have been due to Vodafone UK not allowing tethering/hotspot, but I haven’t found any indication that this is the case so I still think that the described ‘hack’ is a fine solution.
I had a similar problem when I moved from FP2 to FP3 (France, Bouygues telecom). the phone could talk to the internet, devices could make wifi connections to the phone, but devices couldn’t talk to the internet. looked like a NAT problem. However it’s all been working OK since the last Fairphone update.