The only location where it seemed to work just fine was at our datacenter colo, which enjoys a snappy 1Gbps connection. The slower the internet connection at our local office though, the more likely the download was the get interrupted.
While Microsoft continually referred to this as "network issues" on our end, that just wasn't the case. From any other site (even SkyDrive), large downloads work flawlessly, and these downloads from SharePoint consistently fail.
The workaround was to disable TCP Auto Tuning on our machines by opening an administrator command prompt and entering the following:
netsh int tcp set global autotuninglevel=disabled
Auto Tuning is a feature that scales the TCP window dynamically. You can read more at this KB article: http://support.microsoft.com/kb/947239
The takeaway from that article is the following paragraph:
"If you enable Receive Window Auto-Tuning for WinHTTP traffic, data transfers over the network may be more efficient. However, in some cases you might experience slower data transfers or loss of connectivity if your network uses an older router and firewall that does not support this feature. For example, when you use Windows Internet Explorer to access applications that are hosted in Microsoft Office SharePoint Server, the HTTP traffic may slow down. This occurs because certain routers do not support the Receive Window Auto-Tuning feature."Hopefully this is something that will be addressed in a future release/update of SharePoint Online, but as of 6/19/2013 it is still an issue for us.