Qantas is free to join from outside Aus/NZ, its easy enough to change later to your Aussie address.

Air Berlin's TopBonus can be good if you are going to be flying around Australia using Qantas and Virgin as both can be credited, but virgin only earns miles.

AAdvantage are the best for redemptions just now, but this is very likely to change soon.

I'm still using BAEC over here, but am thinking of changing.