depends on what your interests are. i know when i went, a lot of students interested most in surfing and going to the beach went to the university of wollongong.
if you go to the big cities, you won't really get the authentic aussie experience since they are so many people from all over the globe there, not just aussies.
my own experience was in adelaide, which is among the smallest of the capitol cities, and i found myself hanging out mostly with other international students, most of which were from Scandinavia. not that I could possibly complain about my roommates being composed of 2 danish blonde chicks and a swedish blonde chick), but if i was looking to hang with danes, swedes, and norwegians i wouldnt have gone to australia. i finally hooked up with this aussie chick at the uni bar and with that made my way into real aussie life. it probably most depends on your personality though and for what you are looking.
i was not preparing to study medicine back then. if i were to do it again, i'd probably try my hardest to go the university of melbourne as they have what i consider the best med school in aus. there are lots of medical research institutes and hospitals there. you could probably even take some basic science courses with the undergrad entry med students, just make sure you complete all your required premed courses in the US though.
keep in mind the difference in seasons. i went during the fall semester of the US academic calendar, so most of the time i was there was during their winter. not the best for beach going, but again, that will depend on where you go. if you went some place like james cook uni (which the only med school in northern Queensland), its probably beach going weather year round. of course its pretty isolated from the rest of australia as is the city of Perth.