How long do Garmin's cycling GPS devices take to get an initial GPS lock? I've been using a CatEye Stealth 50 GPS device to record some of my longer rides. I've not been using it for commuting though because my commute is only ~30 minutes, and the CatEye takes 3-5 minutes to start recording data. I don't want to add 10% to my commute time just for GPS lock :)*

Would upgrading to one of the Garmin devices like an Edge 500/510/800/810 make a significant difference in initial lock time? (I'm somewhat spoiled by my cell phone and car that achieve locks almost instantly)

* That said, the CatEye was only $150, and at that price I couldn't be happier with its performance.
All of the Garmin/Cateye devices have similar GPS hardware and will take similar amounts of time to get a lock. I don't think upgrading to another device is going to help you there.

Your cell phone is faster because it uses A-GPS, which uses the cell tower data stream to download GPS ephemeris and almanac data.

I asked a question a while ago about how to optimise getting a lock which might help you out.

I've found it best that after the GPS is turned on, it's best not to move until it gets a lock. If it's downloading and constantly getting interrupted by moving buildings, it takes a lot longer to get a lock.