Do you have a smart watch connected via Bluetooth?
Edit: Also I just turned off the toggle for "Phone Calls" under the Bluetooth settings for my earphones... have not had issues yet....
I decided to try this after I had Watch still off audio would only not work on first connect, if I disconnected and reconnected without watch on i did not have the issue for over 30 mins...but then got a call answered fine on earphones but once call was over Spotify was playing still but no audio again, so tested turning off phone call option for the earphones and seems to be holding so far on a few tries...also no more dead air on first connect fingers crossed.