You are probably correct that AC/DC and Cold Chisel are the two near-universally loved bands in Australia, but you could certainly add the Easybeats and Midnight Oil to that list too. (Of course, Australians are probably thinking of Bon Scott's AC/DC, or at least nothing much after Back in Black.) There's also John Farnham (massively popular but a bit embarrassing) and Paul Kelly (not as rich, sure, but probably considered our finest ever songwriter).
The most popular Australia bands of recent years would be silverchair and Powderfinger, but they are probably too recent to acquire that kind of legend status.
Beyond these, there are any number of great Australia acts whose popularity (or cult status) has more or less endured. Off the top of my head: Johnny O'Keefe, Seekers, Billy Thorpe, Daddy Cool, Masters Apprentices, Skyhooks, Little River Band, Angels, Australian Crawl, Hoodoo Gurus, Saints, Radio Birdman, Divinyls, Men At Work, Hunters & Collectors, Nick Cave, INXS, Models, Jimmy Barnes, Go-Betweens, Icehouse, Cruel Sea, You Am I, Regurgitator, etc.
On the other hand, some bands fall out of fashion, and it's almost like they never existed. Sherbert would be the classic case, or the Zoot (with Rick Springfield on guitar).
And don't get me started on all those wonderful New Zealand-ish acts that *become* Australian: Dragon, Split Enz, Crowded House, Dave Dobbyn...
Anyway, here is the ARIA Hall Of Fame. It should give you some idea: