Melbourne born & bred but to be fair its quite some time since i've lived there, i'm based in Copenhagen now.
Depends what you're looking for Erik ??? Forget loppis market lucky finds , everyone googles everything down these days to know what they are looking at. You'd be incredibly lucky to find a bargain.
If you're after new watches then the city center has every brand with Authorised Dealers you're after.
Airport is a little more limited for choice. Do your research into your preferred brand & then purchase not too long before leaving Australia. With your receipts in hand you can get refunded the sales tax but it can take up to 4 weeks to receive the funds.
My local vintage watch shop has a basic offering of watches - mostly 3 hand Omega's from the 50's & very rarely ever any chronographs. Never Heuer.
Owner is a passionate clock maker/ collector. ( focus upon clocks, not watches )
It took me some time to build a frienship talking about my own passion ( Heuer ) before he opened up to me but he's an interesting grumpy old man
http://www.ftgwatch.com.au
Hope thats helped you - Darren