After looking at quite a few threads on this, I found a fix, at least in my case. I have an HTPC on a Sony receiver with a 5.1 setup an AMD HDMI drivers, though I suspect the fix is pretty universal, so long as your receiver can do ProLogic (PL) II, or really any "music" output on more than 2 channels.
Set the receiver to PL II Music and the speaker output on the PC to "Stereo" (Right-click your speaker icon in the lower-right-hand side of the taskbar, click "Playback Devices", change to "Stereo".
You're not losing anything because music isn't recorded in 5.1, it's recorded in stereo. Your receiver will take the stereo input and, if it is setup correctly for PL II Music, split it between your 5 full range speakers, and send the low frequencies to your sub, as is its job, because that's what PL II Music means.
Basically you're just defeating the standard that Spotify is somehow screwing up.
Other applications output music as stereo, so you don't have to make this adjustment. It just outputs as stereo, Windows passes it on as stereo, your receiver receives it as stereo, and PL II Music dictates that it will split that between the 5 speakers and send the low frequencies to the sub.
Spotify is doing something else, which is fouling the normal operation of things.
This will probably work with other "stereo" modes on receivers that handle more than 2 speakers since this is basic audio stuff for almost half a century now. No reason to use software to do this - your receiver does it better.
The only downside is that you have to switch the setting back when you want to watch a movie, otherwise you won't get surround (5.1), you'll get your movie in 2.1, and the voices won't be properly routed to the center channel, with some of the lower voice frequencies going to the sub. You don't want that, so make sure you change it back. Maybe there's a script that can be written to change this setting in Windows when Spotify launches, and change it back when Spotify closes, but I'm not sure how useful that would be since Spotify stays running on many people's computers.
Spotify devs could fix this by simply outputting to stereo only. I don't know what their codec is currently doing, but apparently it's not that.