Or the Bluetooth connection works, but does random things you can't change. The last rental car I had, upon connection, forced Spotify to re-open and start playing the last playlist. Even if Spotify was closed.

Some entertaining solutions I found online include a playlist that includes only silent tracks and switching to that playlist before you turn off the car, or canceling Spotify Premium so you can no longer download/cache songs, giving you enough time to mute before Spotify's cloud can stream the song to the car.