Generally speaking, Telecom XT will provide better coverage1. You will need an 850MHz WCDMA (3G) device to use their network.

To get the best coverage using Vodafone, you must have a device which can support 900MHz GSM + 900MHz WCDMA (3G) + 2100MHz 3G.

However, both VFNZ and TNZ are usually more expensive than 2degrees, which has its own network in some cities and roams on Vodafone in others.

There will be parts of your route where there will be no coverage at all from any operator, however this is likely to be limited to stretches of highway. You'll have coverage in the townships and cities and along parts of the highway corridors. I'd recommend having a smartphone based GPS - you could look at a MiFi or similar if you've got a few devices to use. While you don't really need a GPS for getting between cities, getting around IN a city can be confusing, particularly Auckland and Wellington.

1 - This is due to their 850MHz frequency which travels further and penetrates buildings better, and they tried hard to replicate their CDMA coverage footprint