There's a corner case where users who have never visited your domain (either ever or just on that browser) do so for the first time over a malicious connection. In this case, Mal sends them a page that looks reasonable, they create an account or login or whatever, Mal gets the password and probably proxies the requests to the origin domain (properly over https so even if the site operator redirects all pages to https, this still works) so that the user gets the email confirmation or whatever.

A tiny bit better is to submit your domain to https://hstspreload.org/ so that (major) browsers force https on the first connection. You should still set the HSTS header of course, it's a requirement for inclusion in the preload list and it should also catch people who have a browser from before your inclusion in the list or browsers that don't support the preload list at all.

You could also choose names whose parent domain is already HSTS pre-loaded. The .dev TLD is pre-loaded for example.

What happens if your browser (eg. new device, another browser, first visit) does not have a record of HSTS data for a domain, and you visit it by going to HTTP on an insecure network?

Can't they similarly serve HTTP data without any HSTS headers? Or do browsers also check HTTPS for any HSTS headers on the same IP and cross-compare?