I recently moved to New York, but have been loyal to AC's FFP for the past 4 or 5 years while based in Sydney. I found that worked well for me, as I would often only just scrape in enough miles to requalify for *G. I flew NZ a lot across the Tasman, and the status really made a difference - very, very quick checkin and security and (for the most part) excellent lounges.

During that time I used a number of the Asian *A airlines plus AC to fly to/from North America. AC doesn't allow *any* mileage upgrades, but it does give out upgrade certs to elites, however AC only fly their own metal to SYD so that might not be terribly user friendly for you. Plus you don't really want to have to connect through Canada to California. However AC does have better award availability than UA on other Star airlines - and let's be honest, if you're redeeming your hard-earned miles you will almost certainly want to be doing so on other airlines!! Another nice thing about AC's program is that they don't require you to fly on AC metal at all to maintain your status. Plus redeeming awards online is reasonably easy, and if redeeming on NZ (such as the excellent value business class Australia to South Pacific award for 35K miles) you don't even have to pay any taxes.

So if free upgrades aren't your priority, in terms of economy class experience longhaul NZ is absolutely one of the best there is, and significantly more pleasant than QF (and more comfortable, if on a 744) IMHO. Plus their lounges are excellent, and they are pretty good at recognizing *G (with priority seating, exit row access etc). Their connections from MEL to California are pretty good too - although QF does have some nonstops MEL-LAX, beware the dreaded SYD transits between international and domestic, they are a pain in the proverbial. An international to international transit at AKL is a much easier and less time consuming proposition. Having said that, I wouldn't recommend that you actually change to NZ's FFP, unless you're buying lots of high fare classes (and even then I'm not sure it would be worth it).

For travel in the other direction, SQ, TG and OZ (from SYD only) are all reasonably good options. None are known for giving out free upgrades even to their own elites, so I don't think you miss out on much by being elite in someone else's FFP rather than theirs.

Domestically, you will probably find yourself flying QF a bit, but it's not a generous program so you might find that splashing out on QF club membership is worth it. I find Virgin pretty much the equal of QF domestically but for less $$$ - they are a well-run airline with a good customer service mentality. You can easily get credit cards that will earn you points for either airline. As for Jetstar, I avoid them like the plague: cramped seating, often inconvenient airports (especially in Melbourne), and rigidly enforced rules. I can't speak for Tiger, I've never tried them.