Hmmm... never seem to have the time to write about this trip to Australia, so here are some recommendations.
Overview: we went visited Melbourne, Sydney, and Cairns over a two week period. Two weeks is just enough to cover this, and with the exception of changing the return flight a tiny bit, I'd recommend this order.
Flights;
We flew Qantas LAX-MLB-SYD-CNS-SYD-LAX. Flying is sort of like it was in the US 10 years ago on a decent airline of the time: nice service. Food on the flights (well, one difference: the food on Qantas is actually edible). No need to arrive 6 hours early at the airport for pointless security checks, although international flights still require some time. The one routing change I would make would be to return CNS-MLB-LAX. Why? Because you can fly later from Cairns to Melbourne than you can Sydney, thus giving you some extra time to spend doing something interesting rather than marooned in the airport.
Lodging Review:
Melbourne: Grand Hyatt Melbourne. Built in the mid-80's and it shows: fake marble bathrooms, brass, padded walls. But I liked the hotel. It has one of the nicest swimming pools I've ever swam in, the standard in Australia appears to be salted pools, and warm ones at that. I don't usually swim at all but made a trip to the small pool almost every morning. The location is central, the service is good.
Sydney: InterContinental. One of the expensive hotels, but I didn't like it. Good service (though not great), 1982 and overdue for a 'soft rehab' (scheduled any day now) not only because the furnishings appear worn, but frankly many of them smell of many years of human usage and a touch of mold. Quiet location, close to the opera and circular quay, I might personally go for one of the apartment hotels a bit closer to the 'action'.
Cairns: Actually Palm Cove (25 minutes north of town, and supposedly the nicest beach). Angsana Resort Great Barrier Reef. Disappointing. Not bad, but this place is made out to be a luxurious spa but in fact feels more like a timeshare. It's sold as the only place directly on the beach, but is in fact the furthest hotel from the stinger net (which is dangerous to swim outside of most of the year). The suites have kitchen, laundry, one big bedroom with two bathrooms (I'm guessing a 2-bedroom suite has this same room split in half). Remarkably uncomfortable beds and pillows. Currently apparently converting to condos, beware they may be jackhammering or rotodrilling during the day without notice. Decent Thai-staffed spa (Angsana is related to the Banyan Tree chain).
Sydney Airport: Holiday Inn. Exactly what you'd expect.
Tours:
Melbourne - Great Ocean Road - 12 Apostles. It's so hard to find an excellent personalized tour guide. We went with Aussie Mates Tours, found on the web. Mark (the owner/operator) is a friendly local who loves to show people around his neck of the woods. He's quite new to the business (what a time to enter the tourist business, eh?), but as he picks up polish over the next few years he should be pretty good. I do wish he had more comfortable seats in his vehicle however!
I'd recommend a personalized tour like this because with a few people you can go where you want, and he has access to some places at hours where and when big groups can't go. We visited a wildlife refuge for the kangaroos, wallabies, the Cape Otway lighthouse for ocean views, a walk in the woods to find koalas, and of course a quick viewing of the twelve apostles as the sun set. It was a stormy day, and a visit to the loch ard canyon and some of the nearby holes was quite a dramatic demonstration of the power of the sea--as dramatic as our guide had ever seen it.
Do note this is a 12 hour day, so start early--if it's the start of your trip the jet lag should help you get up early in the morning!
Cairns - Great Barrier Reef: We went with Reef Magic; again by finding them on the web and shooting them some email. I like places which can respond with good humor. This was a great trip. Admittedly a trip I took in Thailand at the same price had 1/8 as many people aboard and a bit more formal diving instruction, but the real point here was to visit the below-surface world at depths shallow enough you could swim to the surface if need be. We went on three dives--the first short dive (free, 20 minutes; ask the companies what their intro dive is no matter if it's free or expensive), and two half-hour dives extra. The dive master stole my camera for the last dive, but her pictures came out so much better than mine!
Food:
This is the longest topic. We ate at lots of expensive places, but I think my general rule still holds: I prefer dives with good food to formal bland places. We didn't really go to the latter, but stayed between the two, with mixed results. Someday I'll write about this... Of brief note, Ondine (MLB) was expensive and disapointing (started off very promisingly and ended average), Zaafran (SYD) had Indian food of types I haven't had before.
Money and other miscellany:
If you have a US based calling card, find out the Australian access codes before you go. A US based Costco card is 1/8th the price of what your hotel will charge for a long distance call within Australia. You can also buy a card there, don't know if it would work in the US.
ATMs of course offer the best exchange rate and are widely available.
Internet cafes: Not too hard to find; Melbourne has plenty on Flinders street; in Sydney's Circular Quay neighborhood there are a few, including one in a supermarket on I believe Pitt street. In Palm Cove, the Angsana resort has a cheap automated machine believe it or not.