I have the same experience with many Bluetooth devices, but I have to say that my Bose QC35 headphones are almost flawless. Definitely one of the greatest things I ever bought.
They even handle gracefully playing music from my laptop and when I shut it down, they automatically reconnect to my phone without any interaction. This sounds simple but I've had many pains with similar stuff with previous devices.