Early Austronesian expansion into Australia somehow. Maybe a small population goes to the area around Cairns QLD or a bit north and blends with the Aboriginals, and later on this cultural fusion spreads far to the south and you get some (delayed) Lands of Red and Gold style agriculture. Something involving Papua and the Torres Strait Islanders might work too, or maybe both.
Pretty much the only way to have an Aboriginal majority in Australia is either more advanced/integrated coastal Papua leading to expansion and cultural fusion (not displacement), some Indonesian group's expansion leading to cultural fusion (and not displacement) or (much) future Indonesian colonization, or indigenous agriculture LoRaG style.
Uh, you do realize that Australian Aboriginals actually have it worse than Native Americans when it comes to European diseases yes?
Full blooded Native Tasmanians are extinct, and so does many Aborigine tribes that exists solely on their artifacts. Diseases hit them worse than Native Americans because unlike Native Americans who have basic hygienic practices, Australian Aborigines never developed that pre-European contact.
Source on this? Native Tasmanians are extinct because they had small numbers and were deliberately targeted for genocide, something which was rarer in the Americas (and most successful in places like California where some native groups were also small-numbered).
Like American Indians they did have that lack of immunity due to isolation but I've never heard of the idea they were even weaker or that it was because of their hygiene practices. It isn't like American Indian sweat lodges were very good for dealing with measles, smallpox, etc.
If you want to cite higher death rates, it's less biological and more because hunter gatherer societies are more vulnerable than agricultural societies (like those of the Mesoamerica/Andes and to a lesser extant the East Coast of North America) due to low population densities and the fact that killing just a few members of the band leads to important loss of knowledge and skills.