Depending on where you are coming from and what you think of as warm water June/July is great for swimming on the Great Barrier Reef up north near Cairns, might be a bit cold further south (eg Herron Island) and much too cold on the Gold Coast and further south.
Australia north to south is about the same as San Diego-Seattle - best beach weather in San Diego is not the same time of year as best beach weather in Seattle
If it is just a 3 week holiday, I'd say keep to your original time of Oct-Nov, say mid Oct - early Nov, starting on the Great Barrier Reef and then heading south. Sept-Oct and you get Australian school holidays early Oct with limited availability.
I'd say Cairns or Port Douglas (Great Barrier Reef, Daintree, Atherton Tablelands) and Sydney (Blue Mountains, Grand Pacific Drive, zoo...). Port Douglas is north of Cairns, it has a beach, but it's pretty quiet, a lot of the tours go through it so you still have a lot of options for daytrips; Cairns, not really beach, more about what there is available to do. 3rd spot, depends - how many of you? ages? interests? Do you want to see any major attraction (other than the Great Barrier Reef)? Major attractions I mean Kangaroo Island, Uluru, Kakadu, Great Ocean Road, some people are anxious to see Coober Pedy. Or do you just want a good beach with water temp of how many degrees? (Cairns is more about going on trips to the surrounding sites rather than a lounging on a beach)
Gold Coast is lively, theme parks, probably a cross between Orlando and Daytona, A lot of the timeshares are towards the south of the Gold Coast where it is a bit quieter.
Sunshine Coast is a bit more grown up, not that many timeshares.
NSW mid north coast has quite a few timeshares too around Coffs Harbour and Port Macquarie, more laze on the beach spots, though there are daytrips to the hinterland.
Going south of Sydney it will be a bit colder in Oct.
If you check on the old board, there were quite a lot of Australian threads from when Judy was planning their Australian trip in 2006 or 2007??