Easy choice: Melbourne. Fireworks over the Yarra (not quite as spectacular as Sydney harbour) but makes up for it with lots better food at restaurant NYE events and hotel prices that are half Sydney's. Pretty good party (maybe better given the lack of the insane Quay crowding).
Other option is to go very isolated. Southern Ocean Lodge is great for that, but expensive ($1000+ per day).