Depends on the phone. The Droid was pretty timely for Froyo as was the Incredible. The Droid X/2 was a little slower, but acceptable as it was pretty solid when it hit. The Fascinate, forget it, plagued like the other Galaxy S.
Depends on a bunch of things, probably most importantly is the relationship between VZW and the manufacturer. Remember, there are two chefs in the kitchen when it comes to carrier OTA updates. That's never the quickest way to go.