I changed phones and when I connected my new phone to my existing Gear S3, I had to "switch" the pairing to the new phone. I also installed a new Gear S3 update, which basically wiped my Gear.
1. I paired the Gear with my new phone and this automatically transferred my phone's saved Wi-Fi credentials to the Gear. This is an option you can turn off (in "Sync phone settings" on the Wear app on your phone). However, if these credentials are transferred when pairing the phone and the Gear, don't worry, we can fix this.
2. I downloaded Spotify for the Gear. During installation, I had the option to log in to Spotify using the Spotify credentials on my phone and it then asked me to input a 4-digit code, rather than my user name and password.
3. PROBLEM: After all this, Spotify would only download over Bluetooth when connected with the phone, and really slowly at that (if at all). If I turned off Blutetooth hoping to download over WiFi, my playlists would be inaccessible and nothing would download. It was as though the Spotify app was dependent on a connection with my phone. It also appeared that even though the Gear said I was connected to WiFi, it was pretty obvious it wasn't.
4. Disconnect your watch from your phone by turning Bluetooth off on your phone.
5. Log out of Spotify on your watch. Log back in ON YOUR WATCH using your user name and password.
6. Also on your watch, find your network connection and tell the watch to forget it, not just disconnect, but "FORGET" the network. Now, rescan for networks, connect to your WiFi network and reinsert the password, once again on the watch.
7. Spotify immediately started appearing correctly, playlists and everything, as soon as I did this. It also started downloading over WiFi when not connected to the phone.
8. Turn Bluetooth back on on your phone and everything should still work smoothly. Hurrah!
This worked for me.
On a separate note, I have found that downloaded watch faces tend to make your battery drain much faster. It's a shame, but I have had to stick to the pre-installed faces.