How to fix the slow apt-get update issue on Linux machines

Over the last month, an odd issue tripped up Linux distributions that use apt-get for updating and upgrading. Upon issuing the command sudo apt-get update, the process would stall when connecting with any of the default repositories or slow to a crawl when downloading headers during the update process.

After much troubleshooting and chasing down the wrong rabbit holes (such as DNS, cache, and gateway issues), I finally discovered the problem. You may be surprised at the solution.