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.
Preload lists are not a realistic solution (you can't preload the whole internet) and a sufficiently complicated site will be subverted due to 3rd party dependencies. And does uninstalling a browser not clear the hsts cache?
Perfect is the enemy of good. A large portion of sensitive traffic is protected by HSTS today, and the preload list compresses well. By the time it'll become a problem, we'll hopefully be at the stage where HTTP is treated as insecure anyway.
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.
I'm not saying it's a massive hole, i'm saying it's an easily preventable hole that the entire industry is ignoring for unknown reasons. One simple URI change could make HSTS obsolete and fix the hole with no need for awkward workarounds and half-measures. Nobody has yet explained to me why "good enough" is better than "fixed".
You can't preload the whole internet, but by getting the top xx thousand you get 99% of all Chrome users traffic. Its not perfect, but it is very, very effective.
[1]: https://hstspreload.org/