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.