If a cafe (or similar) I would ask if it okay to leave the book. I have never had a refusal, although one person once put a limit of two books. Often the staff claim the book saying they want to read it. (I wish though they had been as eager to log it, as despite saying they would log it, they never have. But at least the book went to a new reader.)
I don't leave books too close to rubbish bins, as it might be tempting for someone to throw it out. I mean, I once had a book picked up and posted by someone. But at least that one was logged by the finder in the mail sorting, one or two hundred kms away :) They were as surprised to find the book in the mail, as I was to read it had been posted.
I can't imagine the beach having cleaners/security, but then, I don't know the beaches of Perth. The amphitheatre sounds a good place. Also benches, stone walls, boulders and the like are good.
In places like that I usually pick the place because it's photogenic, as I like to take release photographs. In front of the ocean, or a colourful cafe/shop, etc.
I have released the book at a beachside cafe on a table outside facing the Indian Ocean. It is one of those beautiful summer mornings where you feel invigorated. The air feels fresh, the ocean waves gently roll in as the morning surfers depart for a day in the office.
I went for a work along the beach and noticed several people stopped to sit in the amphitheater. I might drop one book off here.
As I came off the beach, I noticed the bus station with several benches. This might be an ideal place too but then a thought hit me about the social demographic of people who take buses. I came up with this awful limitation that these type of people tend not to journal.
Anyway, thank you for dropping by - your considered reply was very much appreciated and I will look into that release challenge. Have a great year!