I called apple, and this is the exact issue for me. The new update is bigger than the space left on my series 3, so my options are to unpair and re-pair the watch (which they'll walk me through) or...get a new one lol. But lacking space for OS updates seems to be an existing issue with series 3 watches. In any case, they said it should be resolved once the update is installed.
For anyone having issues, apple support over the phone was amazing. Spoke to a person in less than 30 seconds of them calling me (which was immediately after I filled out the form). I prefer someone over the phone instead of chat, but I know chat works well too!
I'll likely try the unpair/re-pair process later after work. Support said it could be as fast as five minutes, or take as long as an hour. But I'll update if and when I do!