I've been trying all of the suggestions I could find, but the one that put me over the top was resetting the network configuration on my iPhone (General > Reset > Reset Network Settings). No idea why and there's no way to know if one of the other steps was also necessary. Also of note, I was originally on a 5Ghz-only WiFi network, which this watch (series 3) doesn't support. Switching to a 2.4Ghz WiFi network did allow the watch to get Internet access and I could see it downloading data over HTTP and HTTPS. And yet somehow it wasn't happy until the phone network was set up from scratch. Quite the voyage of discovery.