Hi. I know there are some VPS providers that have hosting out of Australia. And you should find that they can get you the ping times you need since (depending on telecoms' and optus' fickle mood) we usually get <200ms to our au based servers.
If you are looking for provider in US, you will have to look one in West Coast since your traffic from Australia/New Zealand will most likely go through US West Coast. East Coast providers will add latency due to the traffic having to travel pretty much additional ~7000-8000 miles round trip.
Fluid Hosting, LLC - HSphere Shared and Reseller hosting - Now with HIGH AVAILABILITY Fluid VPS - Linux and Windows Virtuozzo VPS - Enterprise VPS with up to 2 GB guaranteed memory! Get your N+1 High Availability Enterprise Cloud Equinix Secaucus NY2 (NYC Metro)