The domestic portions within Australia are the least of your worries to be sure. You can redeem AA miles (if you have them) or BA miles (super easy to get) for travel on Qantas. Focus on getting to Australia.

If you're going to be ready to book soon and a ticket short, I'd say buy some US Airways miles (110K for J to Australia, allows routing via Asia with a stopover in Asia). That's definitely a sweet spot for any program.

Really it depends on what you have and how flexible you can be. If you want to fly to NZ the only way to snag premium seats that lie flat really is from NRT-AKL (so SFO/LAX/SEA-NRT on NH for instance followed by NRT-AKL on NZ). From AKL to mainland Australia should be a breeze on NZ or QF.

If you're less interested in full-flats SFO/LAX-HNL on UA or PHX-HNL on US followed by HNL-AKL on NZ) is a perfectly reasonable option especially if you're interested in spending some time in HNL on your way down.

Then of course there's routing via elsewhere in Asia -- you could do a lot worse than EVA via TPE (I just flew them a few days ago; they serve Dom in J and have the Cathay style Sicma Aero inverse herringbone seats which are super comfortable). There's always TG via BKK -- a sweet option if you can send >1 person in F so you can all visit the departure lounge for some massages. Via SIN on SQ isn't too difficult if you can make it down to SIN without SQ

This is all assuming you can't find seats on SFO/LAX-SYD with UA or YVR-SYD on AC.

Finally, Alaska has the same access to QF awards as QF's own members (that is to say you can book them before AA frequent fliers have the chance, as soon as Qantas loads the schedule; I can't remember how many days out that is).

I guess what I'm trying to say is: For J-class travel, the above. For F-class travel, forget UA, it's just not worth it over the above options. If you want to fly F, try and get a hold of QF, NH, OZ, TG or even the new CA product out of LAX and fly via Asia.