By all means consider New Zealand. If you and Andy have not been there, for sure go there on vacation.

Andy and I were in new Zealand in 2003 and really enjoyed it. Of course, if it has a port, Andy has probabaly been there multiple times since he was in the Royal navy for almost 14 years.

The one caveat in terms of a place to live is it is very difficult to get a residence visa, or at least it used to be. I'm sure you remember that Lisa Slater (not yet Nicholls) had a heck of a time getting in. Their official position was she was without job prospects in their country. If you get serious about this you should talk to her.

Since Andy is still a British citizen, I believe that he may have right of residence since New Zealand is part of the Commonwealth but I am not sure about that.