ICloud – Can’t connect to any apple servers, third party apps have trouble connecting

Problem
I can't login to iCloud, Itunes, App Store on my Macbook
Accessing the App Store app displays a 'Cannot connect to App Store' message
Attempting to sign in by going to [System Preferences > iCloud] and entering my password results in "There was an error connecting to the Apple ID server"
(On my last attempt it made it to the two step verification step. But after entering the code it hung for some time before the message "Account Details could not be opened because of an error connecting to iCloud."

• I can sign in to apple.com on the same computer through a browser with the same login information just fine.

Context
I've never had this issue before until a few days ago. One day I had issues login through another application (Clip Studio). I also get "steam was unable to sync your files with the steam cloud" message when trying to play games on Steam (another application on my mac). Eventually I tried updating with the App Store but it gave me a "Didn't get a response from the Apple Software Update server" message. My safari is also very very slow now.

Specifications
MacBook Pro (13-inch, 2017, Two Thunderbolt 3 ports)
macOS Mojave
Version 10.14.6 18G6042

What I've tried:

Closing and opening the windows again

Restarting the computer

Double checking that my login info is correct

Restoring mac from time machine backup to an earlier date (what I believed was a couple days before the issue)

[Keychain Access > Preferences > Reset My Default Keychains]

Clear safari cache, clear safari history

Rebooting in safe mode (same issue there)
Creating a new user (same issue there)

Malware bytes scan (no issues)

Completely turned off default firewall (I don't think I have other firewall apps)

Checked Proxy settings
[only Auto Proxy Discovery is checked]