Hi there,
when I was over in NZ I chose
http://www.nationalbank.co.nz/ However, I just opened the account when I was over. I'm not sure whether you can open an account if you're not there in person, I would doubt it but I'm not sure.
If you are based in Germany there are some very nice options of how to get your money there without being charged anything for it (we have a lot of banks who allow withdrawal with credit card for free - so basically you can convert money for free everywhere where you are). For the US I have little idea, though. If you want to sell BTC for NZD feel free to give me a shout - I might well be interested