There's one civilization I've been looking into that's so obscure it's never featured or even been mentioned here on AH.com before- the Rotinese, aka the "Hataholi Lote".
In the same climatological zone as North West Australia, Rote Island is a dry land with few natural springs and subject to an irregular and inadequate monsoon rain, but the Rotinese got around this by forming a complex, hierarchical civilization which revolved around cultivating of the lontar or palmyra palm (Borassus flabellifer L.) for its sap and nectar to circumvent the need for water (but who also dry-cultivated rice, millet and sorghum, as well as keeping domesticated herds of water buffalo, sheep, goats, and horses a long time before the arrival of the Europeans). Two or three trees support each family, with each tree yielding 200-400 litres of juice each year for up to 35 years. And this nectar, known to them as Tuak manis, is the first nutrition that a newborn Rotinese baby receives, even before its mother’s milk. The Rotinese were also renowned for their cakes of crystallised sugar, which they made by baking the juice of the lontar palm; traders regularly visited the island to purchase lontar palm sugar, which was then traded throughout the Indonesian archipelago, and vessels from Roti also sailed to the Tukangbesi islands of Sulawesi Tenggara, selling palm sugar directly to them and picking up ironworking from them.
The closest advanced agricultural civilization to Australia, only slightly further away from mainland Australia as Tasmania (extending to the Ashmore and Cartier Islands, known to the Rotinese as Nusa Solokaek), with a complex imperialistic court-based society that was already adapted to the climate and scarce rainfall, possessing with all of the crops and domesticates one could ask for, as well as iron-working and a number of unique cultural innovations, dating back over a thousand years, with a long history of engaging in naval trade and with artifacts from trade partners as far afield as Song Dynasty China- what's not to like? Aside from the fact that IOTL, they never bothered to sail southwards and settle the continent, in spite of how much easier it would have been for them than anyone else, and how much more vast and powerful their civilization might have become as a result.
So then, what if the leader of one of the Rotinese noble or commoner clans had decided to embark upon a colonial expedition, taking that short 300km voyage across the shallow Timor Sea (less than the distance between Brittany and Ireland) and settling on Australia- bringing their culture, technology, cultivars, domesticates and trade along with them? Let's say that this happens around 1100-1200 CE, around the same time when the Song Dynasty Chinese Porcelain artifacts on Rote island date back to. How big an impact might this have had upon the history of the continent?