"Any time an App Store app gets released or updated, there's a fun game where you watch it slowly propagate to visibility among your friends and acquaintances"
Are you sure that is for technical reasons? I don't see a big advantage of pushing such updates to all customers in one go, and I can see an advantage of staggering updates (say 1% every hour over a couple of days): if your update breaks something, it gives you a fighting chance to at least adjust your web site before all your customers send you mail at the same time.
I'd say that's far outweighed by users complaining that they get odd errors when they try to install the app when it's in a half-propagated state. Heck there was a 5-page macrumors thread of people keeping each other updated on what fun error the Mac App Store was telling them for each country when Mountain Lion was being released. Took a day for it to propagate.
If Amazon CloudFront worked that poorly at replication, everyone would rightly tear them a new one.