Mac Software Updates and App Store don't work over Google Nest wi-fi
Solution 1:
I discovered that the fix for this was to change the Network Location (System Preferences > Network > Location). Mine was set to Automatic, so I created a new location called "Home" and used that.
Even though the Wi-Fi network I was connecting to was the same, this act of changing the location made all the difference and I can now happily perform software updates, load and interact with the App Store, and generally use my network connection for everything I need to use it for.