Sounds like maybe you're not experienced long-haul fliers. Australia is a very long flight. You might consider breaking the trip up- maybe a coupla days in Hawaii or Japan? You could also consider splurging on Business Class seats. I know they're a ton of money, but look for discounts and make that part of the adventure- your body will thank you. If you're a frequent-flier member, you might wind up with miles enough for another (domestic) flight free.

I've been to Australia (Sydney only). My overall impression is that yes, Australia is a great place to visit and I want to go back, but not necessarily to spend a long time in any one place (unless you're beach people). A lot of blank space between things to see/do.

Group tours are hit-or-miss. You've got about a 40% chance of meeting life-long friends and a 75% chance of encountering someone really obnoxious. I know- I've been a tour group leader a few times. You will move at the pace of the slowest person. If that's you- great. If not, be sure to take along your blood pressure meds. Advantages are lower cost (assuming you want to do everything the group does) and convenience- especially in places you don't speak the language. Not the case here. I'd be willing to bet your '10-day tour' would be a whirlwind and then you'd spend the extra two weeks going back to places you'd already been.

For the 3+ weeks mentioned, I recommend booking airfare and hotels in 3-4 cities and finding guides/car as needed for day trips out from those hubs. A good, private, local, day guide is well worth the expense.

That's a long trip- maybe 2 wks in Aus and then one week in NZ?