Internationals NEED to network. The hiring manager needs to feel like you’re ‘the right person’ more so than a citizen/PR. With STEM PhD from an elite school and being in California it never felt too difficult for me, but definitely harder than for citizens.
A lot of my colleagues did a postdoc after PhD, and during those couple of years applied and received EB2 NIW through self-sponsorship, which transitions into permanent residiency, but that route will run you about 10k in legal and filing fees. You need some sort of ‘extraordinary’ basis for EB2 - a PhD and good publication record.
Without an advanced degree I think it’s very difficult unless you end up working for an employer that’s exempt from the lottery, or if you are eligible for other work visas like TN or there’s a similar visa for Australians. Even then, you need to network. A lot of employers will not be thinking that they can bring you onboard on a non-H1B visa, and so they will not consider you.
You pretty much cannot apply to jobs through online portals successfully because a lot of them will have a box to check if you’re authorized to work in the US without sponsorship, and if you click NO (you can’t blatantly lie on an application) then you get automatically screened out by the system. Really really go to job fairs and network hard.