You could start by looking at Citylink, who are based opposite the Dom Post on Boulcott Street. AT&T I think have a present in the city but depends on if their have rack space for hire.

At Nethui last year, there was a hosting discussion around Trademe hosting external clients on their infrastructure and using the capacity and niche that they have for delivering content onshore. Might be work asking them too?

Edit: have a read of this discussion previously about colo space