Hi Walkingman1,
I also find anything above 25 degrees to be too unbearable in the bush for Perth summers and stop walking by about 11am. As you say, early summer mornings are a great time to be out and about, and late afternoon and evening - night walks, especially on trail are fun too. Bold Park and Eagle View are good places. You could also combine this with some star gazing or astrophotography as well.
It's also good to keep an eye on any unseasonal weather patterns - this weekend for example, with possible cyclones up north, there may be a sudden cool changes and rainfall which can be great to take advantage of!
Coastal walks are also good this time of year, and anything near a river or water body is perfect as well.
Other than that, 'down south' is usually cooler this time of year, not guaranteed but usually.
Good luck!