I'm from Melbourne. Here are my suggestions for extended trails in Australia to check out.
1. The Bibbulmun track in WA (960 km). I've only walked a few hours on this track, but it's highly regarded and well worth considering. Best avoided during summer. Spring will be best for the wildflowers.
2. The Heyson Trail in SA (1200 km). See here for more info. Best avoided during summer, at least for the second half that goes through near desert to the Flinders Ranges. There's also a cycle route that runs close by, the Mawson Trail.
3. The Great South West Walk in Victoria (260 km circuit). First half is beach and coastal walking, second half returns through forest along the Glenelg River. Covered in detail in John Chapman's book Bushwalking in Australia.
4. The Alpine Walking Track (650 km) in Victoria and NSW.. This trail goes through all the alpine areas of south-eastern Australia. Avoid during winter and early spring on account of snow. Doing the whole trail will present logistical challenges, but I think these are less so in the southern section. I've done various sections as day or overnight walks. Covered in detail in John Chapman's book Australian Alps Walking Track.
5. The Penguin - Cradle Trail (80 km) linked with the Cradle Mtn - Lake St Clair Track (aka Overland Track) (75 km) in Tasmania. There are many side trips that can be done on the Overland Track segment such as Pine Valley, Walls of Jerusalem, etc, that could double the length and duration of this segment. This is the best hiking in Australia in my view. Best during summer. Often wet. Covered in detail in John Chapman's book Cradle Mountain Lake St Clair.
My experience with these extended walks is limited. The longest walk I've done is in fact the John Muir Trail in the USA. The USA and Europe definitely provide better support for extended hikes than does Australia. There are fewer resupply points here, fewer fellow travellers on the route, and more difficulties in finding the required logistical information. I'd expect to rank the trips as follows. Easy logistics: 3,1,5,2,4. Easy walking: 1,2,3,5,4. Varied scenery: 5,4,1,2,3. Bird watching: 1,3,2,4,5.
I'm happy to answer further questions if I can, as well as provide support if you make it here!