Be glad to be meet up for a drink or two in Brisbane with Murray. I'm currently on a 2 month hiatus from drinking but that's due to end on the weekend (a challenge that I won easily ).

I'm guessing you know how far Uluru is from Brisbane/Sydney/Melbourne right? At least two (more like 3 days drive from Brisbane each way.

At risk of stating the obvious, the beaches are probably something you'd at least want to see. If in Brisbane and going to Fraser, Noosa (nice beaches etc and a bit less touristy than the Gold Coast which is directed towards the Asian market) is basically on the way. Hervey bay (Fraser Island makes HB) is about 3 hours north of Brisbane which is the place to go for whale watching. Dunno what sort of stuff you're into exactly.

Further north is the Great Barrier Reef for snorkelling etc.

Can't really help with gotta see places down south so much. Paulway on here is in Melbourne I think.