First of all I would try to spend a couple of days in Singapore if you have not been there already. That is such an exotic place and much history at Changi prison. They also have fantastic botanical gardens there, just don’t spit or chew gum!
You are coming to Darwin at the right time of the year. That season is Gurrung, you can read about it here. You should definitely plan on going to Kakadu and Andy Ralph and family have Kakadu Culture Camp, the site that gives you the seasons. He, Freddie, Douglas, Dell, Jenny and Catherine will give you a real taste of aboriginal life and the night time boat ride hunting for crocs is fun too. If you are lucky they will be having a bush tucker dinner of water buffalo stew, roasted barra in the coals, bush tomatoes and plums. It is all very good. Also in Kakadu an absolute must is the Yellow Waters Cruise. There are many cruises but that one is on the Yellow Waters billabong and it is always spectacular. I prefer the first one in the morning, but the late afternoon one is also wonderful. By the way, Andy can also arrange for a trek into Arnhemland, aboriginal territory where you cannot go without a permit. Lots of people do get a permit, which is expensive and go on their own, but I would not recommend that , you are much better off there with an experienced guide. Andy is a white fella (white fella and black fella are acceptable terms) but his wife Jenny is aboriginal and they know their way around. There are thousands of rock art paintings in Kakadu, many accessible by foot and easily found. In Arnhemland there are even more but less easy to get to, which is where a guide comes in handy. There is not nearly as much rock art, actually very little rock art at Uluru, that is there the dot paintings originated, the top end is the home of the xray painting which is the type of most rock art. If you want to read about rock art, George Chaloupka is the absolute expert as nominated by the aboriginal people themselves. You can google him and learn much. He died recently and it was a sad day, he was a lovely man and used apple computers, we got along well! There are 2 places to stay in Kakadu, the Gagudju Crocodile inn in Jabiru, nice hotel shaped like a croc, very unique. Or Cooinda Lodge at Cooinda, that is where Yellow waters cruises are and that is a nice motel as well. Both have excellent restaurants. You must eat lots of barramundi while you are in Kakadu, it is all wild caught and so very good! If you want to go fishing, I can give you the name of a guide in Jabiru. We never went out with him that we didn’t catch a lot of fish no matter the time of the year. I could go on and on about Kakadu but a couple of days there is about as much as you can afford because Darwin and Litchfield are also fantastic places to see. As @Bellatrix said, Mindle market is a must, it is on Sunday and Thursday nights, I like the Thursday nights better, they always seem more lively. Some interesting crafts, wonderful food of every ethnicity you can think of. There is a guy who makes whips and sells them. He always puts on a show and it is fun. But the best part of Mindle, besides the sunset on the beach, is EmDee. This is a white guy but most black fellas agree he plays the didge like no one else! He has a rack of 4 all amplified and his drummer. All the aboriginal people congregate there and the dancing is wild and crazy. Go to youtube and search for Mindle market and EmDee and you can see. You must also have fish and chips down on Stokes Wharf. The deck chair cinema is fun. You must go to the museum there. Great aboriginal art and the stuffed remains of Sweetheart the biggest croc ever caught up that way. He accidentally died during the capture and Dave Linder the guy who caught him still chokes up when he talks about it. He loves crocs. He and his wife Patty have a tour in Kakadu called Animal Tracks, that is good too. Dave is the official keeper of water buffs. They tried to eliminate them from the park because their hooves damage the ecology, but there are still many around. You have to be careful driving because they often come out of the bush and each year it seems a couple of tourists get killed by running into them. Pick up a copy of the book Sweetheart it will tell you the whole story. Darwin was a military target of the Japanese, it was actually bombed and thanks to much help from the bloody yanks came out of it okay. There are many placques and monuments along the esplanade attesting to this. Also several military museums worthwhile visiting. Many galleries in Darwin, some excellent art, aboriginal and otherwise. There is a place on Smith Street Mall call Colours of the Territory, I love that place, always has good stuff. Your wife will like On Safari on Knuckey street. The big gallery on the left on the way out of town, heading towards Kakadu is a good one also, I can’t think of the name. If you want to purchase art, I will PM you the names of artists in Jabiru who will paint what you want. Eliminate the middle man so to speak. That is all I can think of around Darwin at the moment, oh yeah, Saturday morning the market at Parap, that is good too. Again great food and many galleries around Parap to see as well.
Next stop Brisbane, to me just another city. I would look around there quickly then drive to Rainbow Beach and catch the ferry over to Fraser Island. You can also catch a ferry from Hervey Bay, but Rainbow is much more beautiful and unspoiled in my mind. Fraser is a beautiful place, lots of 4 wheeling on the beach, excellent fishing, nice places to stay and the home of practically the last of the pure dingos in Australia. On the mainland they have interbred with feral dogs and it is hard to find a pure one. Much wildlife to see on Fraser. It is cool, you are driving along the beach and a plane will land beside you.
You are driving from Brisbane to Sydney. Every left turn will take you to yet another probably deserted and gorgeous beach. Don’t hesitate to explore. You will pass the Big Pineapple, the Big Crab, the Big Bull, aussies are big on big statues of stuff! So many things to see along that road it is impossible to tell you about them all, but if you want, I will try, let me know.
Sydney of course has the Opera House and Darling Harbour, many galleries and museums, a good zoo and a ferry ride around the harbour and even better a ride out to Parramatta on the river cats is great fun too. Parramatta is very rich is history and is an interesting area. Rosehill race course is there, that’s not real interesting but in that section of the town, just about every house has a race horse in the back yard. In the mornings we would walk the dogs and along would come a strapper with his charge and we would walk together and chat.
Melbourne reminds me of Boston, very staid and solid. Very British, but there are areas that are y oung and vibrant, St Kilda is very alive and hopping. Much street art, even Banksy has done some stuff there. It is the home of the MCG (Melbourne Cricket Ground where Collingwood plays!) Rod Laver arena where the Australian Open is held, so many beautiful beaches but the water is always too damned cold to get in! Bells beach where an international surfing comp is held each year. And of course fantastic galleries, museums and the best asian restaurants on Victoria Street. The free circular pram is fun. It is a very difficult city to drive in because of the prams, you have to get in the far left lane to turn right in some places. Be wary if you drive there.
I see some above have suggested Uluru and that is spine tingling but in the middle of nowhere literally. The only near town is Alice Springs. I love it but don’t go out after dark, it has some sad stuff happening there. There is a movie called Sampson and Delilah all filmed in and around the Alice. It gives you an idea of what that area is like. If you decide to go there, I would fly right to Uluru. Or you can fly into the Alice and go out from there. It is about 450k. Kings Canyon is a must see if you go out and of course Kata Tjuta. But really given your itinerary that is one to save for another time. When in Melbourne you are within a one day drive of Adelaide and that is a unique city. It is a capitol city and quite large but reminds me of a small Texas town. More beautiful beaches too. And if you drive there you could go along the Great Ocean Road. The areas around Melbourne and Adelaide are wine country, one winery after another.
If you have a choice between Darwin or Cairns, I would opt for the time in Darwin. Cairns is sort of like a run down tourist town. It has suffered with the downturn in world economies, starting to look a bit tawdry. The Great Barrier Reef is there of course, but people who dive are telling me that unless you go out on a 3 day or more trip, the diving is really deteriorating because of the damage to the reef. Divers say you are better off going out of Airlie Beach in Qld, but again, a day trip just doesn’t make it. You should come back for another month at another time and explore WA, Perth Broome, etc., explore Uluru and the red center on that trip then fly to far north Queensland. It’s a big damn place.
My fingers are tired or I would tell you more. I love this place. Once you are out of the cities it is like another world!