Earlier quoted context omitted.
I have three Bluetooth headsets (and all cheap, in the ~$100 range), use them with Android phones and Linux computers without any issue. The sound quality is par for the price but pairing, connecting, and disconnecting works just like with wired headphones.
Care to share which ones? I'm trying to find some headsets within that range. I'm not an audiophile, just need to hear, and block out just enough external noise.
https://www.amazon.com/Plantronics-Headphones-Sweat-Resistan...
The batteries last for something like eighteen hours, the audio quality is very good, and I find that they strike a really good balance: I can hear just fine when they're not on, but when I'm playing music I can't hear much of anything. It can also pair to multiple devices (though it calls them all "phones"); if I stop something on my Android phone and start something on my laptop, it does the right thing, and it also has an app for iOS/Android that lets me throw to the correct device (though to get back from a laptop you have to turn its Bluetooth off, which sucks). They're really nice overall.
Similarly I'm a huge fan of their sport headphones. These are the only Bluetooth in-ears I can stand:
https://www.amazon.com/dp/B01JKJN71A
Six to eight hours of play time, completely acceptable audio when they're on, can hear just fine when they're not. They're the most comfortable headphones I've ever had; I often wear them for an entire day without noticing that they're in and I've accidentally gone to meetings with them in more than once. My only complaints are that the QC is not always great (or I got a fake, which is the guess I lean towards) and that there are a couple of firmware revisions, basically all the same but it's jarring to hear the robot lady say something different than the last time--because I have a really bad habit of losing them, I'm on my third set.