If I were you I'd hire a motorhome if your budget will stretch. It's by far the best way to see everything. It's not too cheap, but remember it includes your accommodation and your transport! Also, you are going in the deep 'off-peak' time, so you might get a good deal.
Maui and Britz are the big boys, but try Pacific Horizon - they are about 20% cheaper and were very good for us. There are several other operators who do Transit-sized vans, including http://www.nzmotorhomes.co.nz/home.html who do some nice little 2-berths.
It will not be warm in the winter, but if you stay away from the alpine area in the south, you won't freeze, although remember the climate is similar to the UK, so take some waterproofs!
Can't comment on the bus services, but we saw a lot of the Kiwi Experience ones about.:)
