It may not be exclusive to Verizon but considering that Apple updates are severely affected on my system, yet my next door neighbor with Comcast has no problems whatsoever, I am 100% confident that Verizon is playing a role in my woes. In fact, I updated my wife's iPad to iOS 8 OTA on a relative's Xfinity wifi just to get it completed. Took me about an hour to complete. I came back home, less than a quarter mile away to my lovely FiOS and boom, 15-20 hour download estimate on my rMBP to update my iPad Mini (which I'm saving for last or at least until this issue is resolved). Changing my DNS seemed to work briefly on my rMBP but less than a day later my speeds were back to being slow as molasses. At least I had the opportunity to update both my rMBP and iPad Air before the speed took a nosedive again. Just wish I had updated the Mini too. I figured the problem was resolved and I'd get a chance to update it later.
Judging by several posts I found online (links to two examples posted below), I see I'm not alone in thinking something funny is going on between Apple and Verizon. I won't refute your claim that it is also affecting other providers, because your experience sounds pretty close to mine, but everyone I've encountered with problems in this area has FiOS. Folks around me who subscribe to other ISP's seem fine. The link below to the discussion on dslreports (2nd link) is particularly telling because I read it after trying various troubleshooting steps and was surprised by the number of people who posted in that thread that had identical issues and troubleshooting experiences as me. Several people also mentioned that the problem disappeared after they connected to Apple update through a VPN.
I assumed it was primarily on the East Coast because I have relatives in the West and Midwest with FiOS who have not had any issues.
I called Verizon but that was about as useful as your experience. They didn't even bother pointing fingers. They simply said "if everything else works then I'm getting what I pay for". I promptly replied that as an almost exclusively Apple household, I am most certainly not getting what I pay for if I can't upgrade my software, apply security patches or use my Apple streaming devices. Unfortunately, no one seems interested in fixing the issue, so we're left to find our own solutions.
And that's exactly what I did roughly an hour ago. Comcast will be out to swap my equipment and service in 14 days. Problem solved... At least I hope.
https://discussions.apple.com/thread/6552992
http://www.dslreports.com/forum/r29544596-FIOS-horrible-Apple-download-speeds.