NZ is always the correct answer but is rarely given because it's taken for granted.

Not only close, but NZ was originally slated to join Australia and is indeed named in the original Australian Constitution (that created federation) as one of the original 7 states.

Australians and New Zelalanders don't need a visa to travel either way.

In NZ, I approached the immigration desk with my American partner at the time, they stamped her passport with a visa but said to me I didn't need one.

NZ isn't big enough to think about. Don't tell them because they get very upset.