Are you going to rent a car?
Shoulder seasons are your best bet. We've non-revd SFO to SYD a bunch of times. Avoiding Oz holiday times, especially school holidays and Giftmas/new years will be your best bet.

My wife and I got married nearly 3 years ago and did our honeymoon in Oz in mid April. We were there for about a week and a half and did a one way rental from Brisbane to Sydney. It was awesome! I would highly recommend this. Non revd on Qantas SYD-BNE).

We also visited Queensland (UA SFO-SYD, SYD-CNS on Qantas), staying at Port Douglas and Cooktown Sept/Oct (08). If you can, make every effort to snorkel at the great barrier reef. It is spectacular. You need to avoid going when the stingers (jellyfish) are present.

We had to stay in CNS one night and didn't really care for it. We aren't really city people and near shore water isn't very nice to swim in.

Sydney- My wife has done the bridge walk and said that it is great. I'm too thrifty to pay for it. Spend some time in the botanical garden. It is really nice, and the fruit bats (big, daytime active ones) are very creepy. Sydney is really nice, but very expensive! Bondi and Manly beaches are great.

The Hunter Valley wine region is a couple hours outside of Sydney. We thought that it was fantastic. Be prepared...Aussie shiraz there costs about 2 to 3 times what they do in the US. Oh, in Sydney that pint of delicious beer is about $7 or $8 USD.