Do you know where you'll be heading?QUOTE]
Well, since I am brand new to diving and not super familar with the great dive spots of Australia, the only destination I had in mind is the Barrier Reef. Is flying into Carins the best bet? I will likely start from Melbourne since I will be visiting Phillip Island on this trip as well.
Cairns is your best bet (pronounced 'Cans' for reference.) Most of the best diving, in my opinion, is North of Cairns on the outer reef. Port Douglas is about 45 minutes North of Cairns by bus, which is an excellent jump-off point. From there you can go to Lizard Island, Cod Hole, The Agincourt Reefs, all are stupifyingly awesome. The two boats I mentioned, Silversonic and Poseidon, go to the Agincourt system. The Agincourt system is further out than where most of the day-boats go, which lends itself to less traffic and superior visibility. Also during this time of year the weather is coming in from the North, which means the rarer and more beautiful dive sites become accessible.
The Barrier Reef is a great place to see, if you go to the locations I mentioned you're likely to see lots of smaller fish and animals. Not very common to see big sharks and rays, but plenty of nudibranch and reef fish...also some massive Queensland gropers and Maori Wrasse. If you're interested in large aquatic life, I'd recommend Julian Rocks (which is out of Byron Bay on the Gold Coast.) The Reef is so protected you see a lot less of the big pelagic animals, but it's absolutely stunning regardless.
Also regarding Melbourne, there is some good diving there, however the conditions are not as ideal as you'll find on the reef. The water is much cooler and generally has much more current, that being said there are more wrecks and some big pelagic fish to see. If you do go to Melbourne, definitely go for a dive.