HSTS is trying to protect against a specific kind of Man-in-the-Middle (MITM) attack: when the man in the middle pretends that the website you are trying to access does not support HTTPS.
I believe trying HTTPS first wouldn't help: the MITM would refuse your connection, and your browser will try HTTP after that.
With HSTS, the server tells your browser that it is going to support HTTPS for a while. Now, if your first connection to server is secure (no MITM), from now on your browser will know that this particular domain supports HTTPS. So, it will know something fishy is going on if a MITM tries to pretend otherwise.
Trying HTTPS first would still help a lot in other cases, such as the one in the article. None of the super cookie HSTS techniques would have worked in the first place if the browser had just always tried to use HTTPS first.
Probably other unknown vulnerabilities could be averted by just trying HTTPS first too. Not doing so should be considered bad practice, with or without HSTS.
Probably there will come a time when attempting HTTPS first instead of HTTP for manually-typed URLs without a protocol is the right default, but that's just a subset of the problem.
Because any attacker in the middle can purposefully make the https connection fail, thereby causing all data to be sent in the clear. HSTS and hsts preload makes sure that this can not happen.
Arguably, they already are broken. Plenty of people type in https out of habit already. If your website doesn't handle that correctly, you're in for trouble.
I don't know anybody who types https or http before typing a URL. Some older people I know type www, but even that has decreased in the last 10 or so years.
The worst thing is some websites do understand what HTTPS is but still refused to deploy it, and to handle users who consciously type https://, they deployed a valid HTTPS certificate on the webserver and issues 301s to redirect them back to http://. slashdot.org used to do this, bbc.co.uk still does it, what a shame. I know it's often a stop-gap measure to prepare for the upcoming universal deployment, but it seemed most websites that use this hack don't have any plan to secure their sites.
That's what EFF's HTTPS Everywhere plugin does when set to strict mode.
On a related note, would strict mode thwart HSTS-based cookies?
My current understanding of this technique is that it depends on the victim being able to connect to HTTP. Since strict mode prevents the victim from making normal HTTP connections, I'm inclined to believe that strict mode does help mitigate this kind of tracking.
I believe trying HTTPS first wouldn't help: the MITM would refuse your connection, and your browser will try HTTP after that.
With HSTS, the server tells your browser that it is going to support HTTPS for a while. Now, if your first connection to server is secure (no MITM), from now on your browser will know that this particular domain supports HTTPS. So, it will know something fishy is going on if a MITM tries to pretend otherwise.