We sell within NZ and use NZ Couriers as our courier. They have a Shopify app (Gosweetspot) which manages the shipments including printing the labels. It works very well and is free. We had Fastways before but had to do it with the ShipIt app which was $50/month and was not as good. The other couriers may also have their own apps.
The shipping rates can be set by NZ regions (16 in total). The problem with Shopify is that you can’t set a rural charge to apply automatically as it cannot tell if an address is rural or not. Some apps can do that but are generally not worth the extra cost. You have to offer the rural surcharge at check out. Some customers are honest and click the rural price and other don’t.