When I add a NuGet package (latest version of NuGet and Visual Studio 2015) it hangs at "Attempting to gather dependencies" for ~5 minutes before installing the package. I can point to NuGet.org, our internal server, or a folder on my local machine. All behave exactly the same.
After a lot of digging (I had this issue for a long time before posting) I found the issue. One of the NuGet package sources in my list was down. If I remove that from the list, everything goes smoothly. With it in, it bogs down even if no packages in my packages.config are related to that source.