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.
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.