Some ideas for what to include in your itinerary
Four weeks is my idea of a minimum time to comfortably zip round both islands. Your travel style may vary from mine - you may be happy with longish drives, see the big attraction, and move on. I've seen people take that approach and tour NZ in two weeks. But, to me, a lot of the appeal is being able to linger in a varied landscape and take some time to dig into the detail. I also like hiking, so my trips there are laden with walks, and are light on museums!
I've met people who set out to tour both Australia and New Zealand, and allocated the time according to their relative sizes - so 6 weeks for Aus and 2 weeks for NZ - only to regret it. Australia is a fine place but, forgive me, it's relatively empty - many of the sights are a collection of cities around the edge. NZ, in comparison, is packed with variety. It's said that no-one ever visited New Zealand for its cities, but it does have mountains, lakes, forests, glaciers, volcanoes, hot springs, geysers, fumaroles, Maori culture and their interaction with the British settlers, whales, kiwis, Art Deco, jetboats, bungee jumping and a whole adventure sports scene, fiords, and wine.
If you only have 2 weeks, I'd only visit one island.
The typical visitor may travel from Auckland through the central and southern parts of North Island, then a circuit of South Island ending in Christchurch. (People often skip the East and West parts of North Island (New Plymouth and Gisborne), and Northland beyond Auckland.) This leads to a lot of cars being hired in Auckland and left in Christchurch, so reverse route deals can often be had.
Most people are flying in across a number of time zones, and most international flights come into Auckland. So spend a couple of days here getting over some of your jetlag before trying to drive, then grab an internal flight down to Christchurch.
(Flights also come into Christchurch, and it used to be a lovely city, but currently it's still a bit of a mess following an earthquake a few years back. Personally I'd skip it at present.)
As well as looking round Auckland proper, there are a couple of options to get out further. The coast to coast path connects parks and hills across Auckland, and in particular Mount Eden is a good viewpoint of the city. Or take a ferry from the downtown pier over the Rangitoto Island for a hike up the volcano. There are lava tubes to crawl through, and a little museum about the historic "bachs" or holiday homes on the island.
A number of budget carriers run from Auckland to Christchurch. Once at Christchurch Airport there are a choice of car hire companies. I've previously used Usave and had a bargain with their older-model offers. I'd get a morning flight in and head straight off south. If you want to linger, as well as the city centre there's Akaroa and the Banks Peninsula.
Next to the airport is the excellent International Antarctic Centre. The connection is that most flights to the Antarctic go from here. I recommend it, along with the ride in a Hagglund all terrain vehicle.
There are two routes south: to Dunedin, or via various glacial lakes (Lake Tekapo, Lake Ohau) and Mount Cook to Queenstown. If time is tight I'd skip Dunedin and head straight for Queenstown area.
Dunedin was built by Scottish colonists and has a distinct Scottish influence. There's a scenic drive from here down the Otago Peninsula, and you can visit NZ's only Scottish baronial style castle Larnach Castle. En route to Dunedin you pass the Catlins, a scenic area with plenty of walking.
Queenstown is adrenalin central, and the main hub for fiordland. It can be a love-it-or-hate-it place. It's situated in a stunning location, by the shores of Lake Wakatipu and with views across to the Remarkables mountain range. An adventure sports industry has sprung up, along with plenty of bars, restaurants and shops. The hill at the back of the town has a gondola cable car with a complex at the top - fantastic views. Down the valley is the quieter Glenorchy. People use Queenstown as their base for seeing all of the fiordlands, but from there the big sight Milford Sound is a very long daytrip, and I'd suggest also spending at least a few nights in smaller quieter Te Anau.
New Zealand has a range of Great Walks (multi-day hiking trails), along with loads of day hikes, and in the fiordland area there are plenty of day sections of the Great Walks which you can do. The Department of Conservation website is a good starting point to find these.
At minimum I'd stay two nights in Te Anau, allowing a full day to visit Milford Sound and see some things along the Milford road. The boat trips on the Sound take a couple of hours.
The next stop should be Wanaka, the lovely town that's the main settlement for Mount Aspiring National Park. Again, there are walks aplenty. Try to see a film at the quirky cinema where you can sit in a sofa or an old Morris Minor car.
Heading up the West Coast are the twin glaciers of Fox and Franz Josef. Each has a small town serving it. You can walk to the toe of each glacier, and you can take a helicopter onto them to "heli-hike". Basically they have an "upper icefall" where the ice is flowing downhill, onto a plateau, then down another steep bit into the valley. Where the upper icefall hits the plateau the ice churns in slow motion, creating ice caves. The plateau is relatively stable so helicopters can land here, and walkers can wear crampons and pick their way to the ice caves. Amazing. But expensive.
Heading further up the West Coast, you have the option to go over Arthur's Pass to loop back to Christchurch for those short on time. Otherwise, Pancake Rocks is a popular sight. The towns up the West coast are maybe less of interest.
At the Northern end of South Island, Abel Tasman National Park is the highlight. Pretty beaches, lush forests, and speedboat water-taxis to take you out to a section you can hike back along via the shore. Or to the photogenic Split Apple Rock. A taste of paradise.
For those of a less beachy disposition, the Nelson Lakes National Park has a couple of lakes surrounded by nice mountains with hikes across them which are manageable in a day. It's pretty quiet and overlooked here, I think it's a good place to add in if you have time.
All roads lead to Picton for the ferries to Wellington. But wine-lovers will want to visit the wineries of Marlborough first.
The only thing this route doesn't give you is the whale-watching at Kaikoura. It's between Picton and Christchurch. At the time of writing the road is out due to an earthquake, but that'll be temporary. Offshore there's an undersea current coming from deep waters, and this upwelling brings plenty of nutrients, which is what attracts the whales.
Once on North Island, if you like capital cities spend a little time in Wellington. It's renowned as "Windy Wellington", but can be lovely. Te Papa is the national museum, on a nice spot by the waterfront, and free. The botanic gardens has my personal favourite, the quirky Cable Car Museum, all about the personal cable cars which have been built to make inaccessible building plots around Wellington practical.
Heading north, if architecture is your thing, and in particular Art Deco, then head for Napier. The town was rebuilt following an earthquake, just at the right time for Art Deco to be all the rage, consequently it has the best selection in the Southern hemisphere.
Otherwise, you'll probably be heading next for Tongariro National Park and its trio of volcanoes, made doubly famous in the Lord of the Rings films as Mount Doom. The easiest experience is to head from National Park village up the slopes of Mt Ruapehu by cable car, and from the top station take a short (but awkward on volcanic clinker) walk onto the summit ridge for great views on a clear day across to the other volcanoes. For more intrepid walkers there's the Tongariro Alpine Crossing, which is a strenuous day walk crossing some amazing landforms.
We're now in the geothermal heart of New Zealand, and there are lots of volcanic sights to see from Tongariro to the Bay of Plenty coast. Next up from here is Lake Taupo, followed by Rotorua, while a highlight is the offshore White Island volcano, accessible from Whakatane by boat trip.
Taupo town itself is a decent enough base but the main sight nearby is Huka Falls just north of town, close to Taupo Bungy.
On the road from Taupo to Rotorua is my favourite of the local municipal developed hot springs, Waikite Valley. It was built by the local community council in the 1970s and is a lovely, uncommercialised, hot springs. Admission is about $17. For completely free thermal bathing, near here is a spot known as "Hot & Cold". Off the main road is a loop road to Waiotapu springs, and on the southern bit of this lane is a little bridge with informal parking bays either side. The water here is the confluence of a hot stream and a normal cold river - you can bathe freely, and find the perfect spot where the waters mix to make the right temperature for you.
In Rotorua itself you have the Polynesian spa, the Whakarewarewa Maori Thermal Village, a free thermal walkway by the lake, and free fumarole pits in the local park. Rotorua is tourist-central, hence its nickname Rotovegas.
A popular detour west from the Taupo/Rotorua area is to Otorohanga and the Waitomo gloworm caves, a cave system with water running through so you explore by boat. There's also blackwater rafting for the adrenalin junkies.
Across on the coast, from Whakatane you can visit White Island volcano with White Island Tours; it's a pricy daytrip at $219 but you spend a couple of hours exploring the volcano with plenty of activity going on. The fumes can be a little overwhelming but a gas mask is provided. This is a fascinating experience.
Further up the coast from here is Mount Maunganui, a nice lump of rock with pleasant walks up to the top and a thermal baths at the foot. It's a nice resort with pretty beaches.
Inland, close to Matamata, is the Hobbiton film set used in the Lord of the Rings and Hobbit movies. When it was rebuilt for the Hobbit, it was made to be permanent and is now a great visitor attraction. For Middle Earth fans this is a top pick.
The Coromandel Peninsula is a popular playground as you get back closer to Auckland. At Hot Water Beach there's a hot spring which emerges within the sands, so at the right tide time you can dig your own hot pool in the sands and mix seawater with hot springwater to get a comfortable temperature. But my favourite find in the Coromandel was Driving Creek Railway - built by a local sculptor without bothering with permits, this miniature railway originally took him to collect clay. Now it winds through switchbacks and forests, through cuttings and tunnels built with winebottles he had to empty in pursuit of the project, to the summit where he's built the wooden Eyefull Tower (geddit?).
For those getting back to Auckland with time to spare, a good add-on is heading up to the Bay of Islands. The main town is Paihia, with ferries over to Russell, the original capital of New Zealand. The Waitangi Treaty House is here, where the British arguably conned the natives into signing away their country. Further north is the misnamed Ninety Mile Beach leading to Cape Reinga.
That's a quick tour of NZ including the most common places, but it scratches the surface on a complex country. The roads aren't fast - a lot of the terrain is a volcanic jumble that's hard to lay straight roads through - so don't plan on fast driving times. Outside of Auckland and Wellington don't expect to find motorways. There are amenities for the traveller everywhere, with free public toilets frequently placed along the roads, and lots of friendly backwaters. Hostels and motels are all over the place. Grab a road map and plan your trip in detail.
NZ is a real treat - I hope you enjoy it as much as I do.