I asked an Auckland based friend a response and she gave quite a detailed reply, she's also putting together an information packet about tourism in New Zealand (which I'll see if I can PM you when it's done).
In short, the North island is where the serious urban feel is just like any other major city. She recommended Taupo and Rotura both as a must-see. Also check out Mission Bay, Rangitoto, and Waiheke. North Shore and West Auckland also do provide some sight-seeing (and also kayaking) but isn't as great as the South island.
On the South island, starting in Nelson, heading to Queenstown is a good idea (the latter provides a good skiing opportunity). Christchurch is also nice, Dunedin (where Otago University is located is a student's town), Invercargill, and Wanaka as well.
(personal side note - Don't forget Maori culture!!! It's brilliant!)
Air travel is a good option, but on the south island, most cities are within driving distance, so it would be a good idea to hire a car as you really won't get sick of driving. It all depends on how far in advance you plan your vacation