In Sydney (admittedly cooler but still hot) our house rarely needs AC due to trees. Trees make a big difference!
I grew up in Canberra (which is inland and sits in a valley) it was like living in a giant clay bowl all the heat settles in and is absolutely stagnant not much of a breeze to speak about at all. Summer there was pretty miserable (and winter as well).
I now live on the South Coast of NSW - I can get away with a ceiling fan and opening my windows, we get a regular afternoon sea breeze which cools everything down.