Yes, New Zealand would be a definate to check out.
[I'm biased I live here].
You could also consider Australia, but its harder to get into Australia.

You should find it relatively easy to get a work permit - If you simply arrive here you get a 3 months visitor visa, you can look for work and if you are suitably quialified and get a written job offer from a New Zealand employer you can apply for a work permit while in the country - if you have Information Technology skills you should find it relatively easy to get a job.

There are a couple of IT related website that list jobs on the net - try JobUniverse or Seek IT

However, you may be limited to a maximum stay of 30 months depending on the exact criteria/category you apply under.

You should also find it a interesting place to visit and to work in - ask Mark Lord, he came here about 10 months ago now for climbing etc.

We speak English, we are pretty stable politics wise, no-one carries firearms - [they are not legal to own unless you have a permit and police clearance and you cannot carry/use firearms for self-defense like you can in the US

You would a choice of 4 major cities with Universities to chose from if you wanted to study:
.
listed from North (warmer) to south (colder).

Auckland, Wellington [The capital city], Christchurch and Dunedin

Auckland is you best bet for work as its the largest city - Especially if you're into water sports.

If you are into Winter Sports, like Skiing etc then Christchurch would be a better bet as many good ski-fields are about 1.5 hours drive from there.

Biggest issue you'd face coming from the US is that we drive on the left - like the Brits do, so getting a job as a vehicle driver would not be as simple as turning up and taking a test.
Most paying driving jobs would require you to hold a (local?) driving license for 2 years or more. Not sure you'd want to make a living driving around as the roads are not as good as they should be.

you and your partner could attend a university and given the NZ dollar is worth about 47 cents $US right now you could live well on a modest $US income and/or savings.

However, we have income tax of about 33 cents in the dollar, plus a sales tax of 12.5% on everything [usually included in the price though so you don't notice it].

To find out more about living/working in NZ and the requirements etc visit New Zealand Government Online, Immigration Service website.

One Other thing to note is that we are 220 volt power supply, so none of your US electronics will work here without a step-down to 110 volt transformer.

As we are south of the equator, our seasons are reversed compared to you - i.e. Christmas/New Year happen in summer.