Should I wait for clear views of the sky before turning on my Garmin Edge GPS?
I don't have any experience with that particular unit, but I do have a Garmin Oregon 450, which is a "hiking" GPS, but I find it works great for cycling.  I've found there's 2 important things to getting a lock on satellites. First, as you mention, is a clear view of the sky. The second important thing is don't move.  The faster you are moving the more difficult it is for the unit to lock onto a satellite.  

The best advice is to turn it on before you ride and wait until it has a lock before you start riding. I've found that I don't really need a view of the sky, as I can turn it on in my house or in my garage, and get a signal no problem.  I can't however, turn it on in my office, where there's quite a bit of concrete around me.  

I also find it helps if you turn it on in the last place you turned it off. I think the GPS assumes that it's in the same spot it was last time, and tries to lock onto the same satellites. I find if I travel with the unit turned off, it takes longer to get a signal when I do turn it on.  I don't know if this is how it actually works, but this is how it seems to work for me.

Signal is also affected by where you are on the earth.  It works better when you're closer to the equator. You're in Melbourne, which isn't close to the equator (-38 degrees latitude, but a little closer than I am up in Canada (45 degrees latitude).  I don't think you're far enough that it should be a serious problem.