Most of the retail anime shops in Sydney and Melbourne paradoxically do not stock anime (i.e. DVDs and Blu-rays). Also most don't ship overseas. The items they do sell such as figures and merchandise, you can easily get much cheaper from Amazon.co.jp, AmiAmi or other Japanese online retailers. But I'll list them anyway.
In Melbourne;
One Stop Anime (Figures, merchandise etc.)
Nekocards (Card games)
Critical Hit (Figures, merchandise etc.)
Animasia (Figures, Gunpla etc.)
Hearns Hobbies (General hobby store with about 150 anime related model kits)
Anime Town (in Brunswick, figures, merchandise etc.)
Gundam Universe (way out in Huntingdale, Gunpla shop)
In Sydney;
Anime at Abbotsford (one shop in the CBD in Chinatown, second in Abbotsford, figures, merchandise etc.)
AnimeWorks (in the city, but way down on Broadway in Glebe, figures, merchandise etc.)
Kaika (New anime shop in the CBD, figures, merchandise etc.)
Books Kinokuniya (Japanese book chain, artbooks, manga in Japanese in English, various anime magazines and some Japanese manga anthologies - really expensive shop)
HobbyCo (general hobby store with three shops in Sydney, but the one in the CBD has a really good range of Gunpla, figures and some merchandise)
Hondarake (Obscure Japanese 2nd hand book store chain with shops mostly in Kyushu and one shop in Sydney, go figure. 2nd hand Japanese manga, some DVDs and CDs, the occasional artbook)