How long do Garmin's cycling GPS devices take to get an initial GPS lock?
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.