My top "highlights-that-you-absolutely-can't-miss" list:
Snorkeling off the beach in Exmouth
Ayers Rock and even more so, the Olgas
Wine tasting in the Barossa Valley
4x4ing on Fraser Island
Camping on the beach in Cape Tribulation (Noah's Beach)
A few other highlights that I thought were pretty awesome and probably shouldn't be missed because they are essential to the Australian experience:
Sydney
The parks in Northern Territory - Litchfield, Kakadu and Katherine Gorge
Whitehaven beach in the Whitsundays
The Great Barrier Reef
Great Ocean Road
Byron Bay
Blue Mountains
And then a few things that I thought were pretty cool and if you are in the neighborhood you should check them out:
The Pinnacles Desert
The Devil's Marbles
Coober Pedy
Broome
If you can acquire your own wheels then do it. Having a van will allow you to see so much more since many of Australia's highlights are far from the main road and bus routes. At least 6 of the list I just gave you would have been impossible to see with public transport (or at least in a way that made it a highlight). Another major advantage is that if you have your own van you can camp, which is much much cheaper, than hostels or hotels and is often free. Being able to carry and cook your own food will also save you a bundle. Camping also gets you into the wilderness that makes Australia such a fascinating country.
And it doesn't have to be expensive to get your own vehicle. I figured out that over the course of 11 months and about 25,000kms, my girlfriend and I spent almost the exact same amount buying, maintaining and selling a car, that we would have on bus tickets for the same ride. There are many ways to go about this - first, you can just buy a car. There are many travelers in Perth looking to get rid of their vehicles for cheap and they often come fully loaded with camping gear as a bonus. You can find ads at all the hostels and internet cafes. Or you can just buy a used car out of newspaper ads or car lots the same as you would at home. The major disadvantage of this option is that when the time comes to sell it, you may or may not get a good deal or it may take you a while to get rid of it and if you have to catch a flight then it kind of sucks. Some people just don't want to deal with that hassle.
Another option is to go with one of those guaranteed buy-back dealers like the Traveler's Auto Barn. Basically you buy a used car from them, and assuming you don't destroy the car, they will promise to buy it back from you when you are done. They don't give you a particularly good deal when they buy it back, but if you want to get rid of it in a hurry, then you have no worries. You are also free to sell it on your own for whatever price as far as i know. I've heard mixed reports from other travelers about this service. Some have reported feeling ripped off, and others have said they felt it was a good way to go.
And finally, there is the standard car rentals. There's lots of companies that specialize in vans for backpackers. A couple that I remember seeing often were "Wicked Campervans" and "Backpacker Campervans".
So what you have to do is start doing some research online. Find out prices of all three options based on how long you are going to be in the country and how far you plan to travel, and decide what option will be best for you.