All major browsers implement a HSTS preload list[1] to get around the first connection problem. Manually deleting the HSTS pin for a site is quite involved and not something I'd expect most users to do.
I'm not certain if uninstalling a browser clears the cache (do uninstalled browsers retain their profiles?), but preloaded sites would not be affected - they're included in the browser binary. Either way, let's not act like there's a massive hole in HSTS because there's a possibility that users might go as far as reinstalling their browser to visit a not-preloaded HSTS-enabled site that's being targeted.
"You wouldn't HSTS the whole internet, would you?"
Google: "Hold my beer..."
https://nakedsecurity.sophos.com/2017/10/03/google-is-making...
Right now it's mostly unimportant new domains, but it's a start, and they could convince other domain registrars to follow-suit.