A few thoughts below that may have already been considered.
Could be some background processes going on as the phone "settles in" after powering up for the first time.
If apps were downloading and installing via a Google backup restore when trying to access the Play store then that could have contributed to the slowness as the phone was having to work harder, and use the Verizon network connection for the restore download and Play store access.
I have seen on occasion timeouts when trying to download stuff from Play store, but think those have been due to temporary transient network or Play store infrastructure issues beyond my control.
I heard that on Friday Verizon's activation system was having problems, so there could have been other issues in their network. I assume that when the problem happens for you that you have a strong signal on Verizon. If not, that could account for some of the slower downloads.
Restarting your Note 5 may not hurt if the issue persists.
While this is a third party site (below), if the reports are valid, then it looks like Verizon may be having some network issues. I'm not experiencing it on my iPhone, and have not yet heard from family member with a Note 5 if there is a problem. Yesterday we were in a few stores where signal typically drops to 3G due to the stores being constructed with steel/sheet metal framing. I marked down the 3G to No Signal we noticed to the typical interference that can happen in buildings. Could have been a combination of Verizon network issues and environmental interference.