I'm assuming you've already reviewed all of the troubleshooting steps on my guide below - a page made explicitly for this set of issues.
Are you performing the proper WSUS maintenance including but not limited to running the Server Cleanup Wizard (SCW), declining superseded updates, running the SQL Indexing script, etc.?
To quote myself:
> Just because you’ve installed a new WSUS server, doesn’t mean that it’s clean or optimized; it just means that it’s NEW!
I looked on that page, and there are no optimization or maintenance that is mentioned in that guide.