Smith's is pretty expensive but they're the best LFS in Brisbane hands down, although they're selling Blood Parrots now which is a massive let down. Pet City would have to be my second favourite because they actually stock Eartheaters, but I've seen both dyed and hybrid species there.
WetPetz is also decent if you're chasing something specific.
Aquarama at Stafford, the one Liam is talking about on the intersection (next to Hobbyrama) has great driftwood, but I'd never buy fish from there.
Queenslander? Check out
Queensland Aquarium Forum, very popular trading section especially if you're in SE Queensland.