One other data point on my above description:
It looks like my iPhone Xs Max prefers the 2.4 GHz wireless band instead of the 5.0 GHz band when they are both available (it could be that the router makes this decision, when the iPhone is first connecting to WIFI).
This could be contributing to the problem, i.e. iPhone hands 2.4 GHz WIFI details to the Watch, Watch tries to connect to the 5GHz WIFI (as they have same SSID + password).