Wait till mid Jan for 4G announcements with Telstra on phones. The Samsung Galaxy II with 4G - Its navy blue, you can get it from south korea or hong kong on ebay atm.
Otherwise if you need one now on 3G...
Iphone4S, Samsung Galaxy II, Nexus one *kogan sells it but check the box on arrival, as I had a mate who waited a week and staff had stolen it*.. or the HTC sensation XL - White.. Just looked at it and its beautiful, I know Vodafone have it on a $65 dollar plan for 24 months paying it off.
I have a Iphone4S, siri is great, I can send 20 sms's in the car while driving 30 min to city lol. Watch out for 'Majel', Androids equivalent to Siri coming soon ;-D