I've always gone for Motorola phones. I'm assuming that Australia is using a GSM system. The V66 is a nice compact phone that should run on GSM. The V70 is a flashy phone that will get you lots of looks.
But if you want to sync your phone with your Mac, I think the Sony/Ericcson phones are the only game in town. The T68i looks like a pretty cool phone, but I haven't seen one in use.
BTW, in the US, they're mainly called cell phones. Mobile phones works as well. So does "celly".