My Samsung S6 got to the point where I could not download any new apps in a reasonable length of time. Last night after waiting an hour on a download, I finally gave up and went to bed with the download in progress

and the process completed sometime within the next 5 hours. So I went to Target and talked to the local guru in th electronics department. He explained that sometimes the S6 finds a weak signal and decides that it is in a weak signal area, come hell or high water. Simply restarting the phone doesn't do any good. Here's what he did to get me back in business.
Settings -> Personal -> Backup and Reset -> Reset Network Settings ->
Power off -> Start
Of course you won't be able to do exactly the same thing, because Samsung will upgrade your operating system and the phone's entire menu heirarchy 14 times to hide the Reset Network Settings feature before you read this, but you should be able to accomplish the same feat somehow.