Hi Mike,
Thanks for all of that information and for running through those steps again.
At this point, you may want to talk to your host about what to do in the cases of high volume of users to your site.
In addition, although I have not experience with this, you can try adding a third-party pagination plugin, like this one and see if that helps.
Also, you may want to consider installing the Query Monitor plugin and see if that can give us any more information on the issue.
Let me know how that goes and if you have any other questions on this topic!
Thanks,
Jaime