Ok I found out the easiest way, total time takes about 10 minutes...
First, move or delete all your old photo libraries in Photos app for Mac. I deleted mine because I had 3rd party backups, obviously you shouldn't delete them if you don't. If you move it and it still doesnt show up, just hold the
Option key while you start Photos.
Open it fresh, and it will say it can't locate your library. Click "Create New".. name it something like
Then, go to settings and click 'set as system library', and also enable iCloud sync in settings (make your settings look like photo below). This will download all the photos fresh to this library (which doesnt have existing files so you dont have to worry about duplicates and such).
It will say "Updating X photos", make sure you wait for this step to finish.
However, when it starts saying "Downloading 10,000 photos" then you can move to the next step, you dont have to wait as long as it gets past the 'updating' step.
Select all with command+A, then delete. Go to your trash and then delete again by clicking
It will still be stuck saying "downloading 10,000 photos" although they should now start deleting from iCloud (It took about 5 mins for me before it started removing them)
Once its done removing from iCloud web, just close Photos, and delete the temp library on your harddrive. From there, hold option when you start Photos and choose 'create new'. Youll be starting with a 100% fresh iCloud now.