I am from NZ, now living in London and maybe this will help
Yes, the NZ economy is comparitively small but that is not to say there are no opportunities in the consulting sector. I used to work for Accenture in NZ
Here are a few players in the NZ marker
McKinsey, Booze Allen Hamilton, BCG
Accenture, Unisys (strong presence in public sector), Bearing Point, Datacom (technology), IBM, Hartford Consulting (good presence in the public sector)