The Moeraki Boulders, on the east coast of the South Island.
I'll just describe one day trip we did from Dunedin. We arrived at the superplush Elm Lodge backpackers hostel (US$5/day for a shared room, with the cleanest kitchen, showers and bathrooms you've ever seen) to find the place completely booked out. Fortunately, we met three girls from the Flying Kiwi bus and they were happy to cook us dinner and let us squeeze in with them.
The next morning we three set off on our own for the famous Otago Peninsula, kind of like Napa Valley in landscape but with ocean views almost all the time. At the end of the peninsula we stopped at a fur seal colony where I took frame-filling pictures of seals with a 28mm lens -- I got within three feet of seals despite the "seals bite" signs. Of course, this was all backed by a beautiful rock, seaweed and ocean vista.
After burning a roll of Velvia on the seals, we stopped at the yellow-eyed penguin sanctuary for close-up views of parent penguins coming back from the sea to feed their young. It was fascinating, especially for someone like me who thought that penguins were only in Antarctica.
Then, at 6:30pm, with a mere 3.5 hours of daylight left, we visited the Royal Albatross colony, to see birds with 12' wingspans that fly up to 60mph regularly. This is the only mainland nesting colony for albatrosses and we saw dozens flying and nesting.
Finally, we drove an hour back to Dunedin with views over sunset-splashed views to relax at the hostel.
The backpackers' hostels here are really wonderful. Not only do you get a place to sleep for almost nothing, but you have an instant social life around the kitchen, dining, and common rooms. Of course, you have to like Germans since they are the only folks who've discovered the country.