I have a Debian GNU/Linux virtual server with 25GB disk space and 1TB monthly traffic for $40 USD per year. More than enough for a web site or two. The host - http://eoreality.net/
- specialise in gaming servers, so performance has always been pretty good.
My experience has been that NZ based hosting services are wretchedly expensive compared to what's available if you ship around.