I then switched providers, which also came with more system resources, and GitLab was working without any issues right away. It could have been caused by an oversold node at the previous host, or the slightly higher system specs at the new host made the difference, but I've been running GitLab on that new server for a couple of months now without experiencing those slowdowns again.
If you've noticed a gradual slowdown to the point of pages getting stuck on loading indefinitely, then try to up the system specs a bit, as it could make quite the difference.