The best skies I ever saw was here
http://maps.google.com.au/maps?hl=en...,0.694885&z=11
to the east Wilsons prom (no lights) south and west, ocean (no lights) and it is quite far from Melbourne.
Waratah bay was where I had the best views by far ever!