LKL I'd thought for sure you'd opened a giant can of worms on this one! The competition between Aus & NZ (our 9th state ;) is rather friendly, but at the same time fierce!
Septembers a great time for travel in most parts of Aus. I grew up in North Queensland around the Great Barrier Reef & it's a lovely time of year up there, although it's always going to be fairly tropical & a lil humid no matter what time of year. From what you've explained re your fiance's holiday preferences Sydney's not gonna be the place for her on honeymoon. It's a great city and all, lots of buzz and all that, but not the best for one-on-one romance. Cairns or Port Douglas could be a winner, nice beaches, resorts, rainforrests etc. As could Long Island, South Mole Island, Hamilton Island, Great Keppel Island and dozens of others around that region off Queensland. You could always Island hop as most do to mix it up a bit.
NZ's still a bit chilly that time of year, ski season only really starts to finish in late August. Beautiful place though.
There's always Fiji, Vanuatu or southern Thailand (Phuket)?
Enjoy coming to a happy compromise!! frog x