Honestly my linux desktop (Ubuntu 22.04) is where I run into the fewest issues regarding my bluetooth headphones. I've never had an issue connecting to them.
I've had issues where every other time I connect my Sony XM5 to Ubuntu 22.04, it decides to use HFP instead of A2DP which has significantly worse audio quality for music. I need to reset Bluetooth to fix it. None of the solutions online for disabling this "helpful" feature work.
This was quite an annoyance for me too. I discovered/noticed two things, but I'm on Manjaro, so YMMV:
Whether A2DP or HFP is used can be controlled by changing the profile (or whatever it's called) of the audio device, in the audio settings. Take a look in the settings where you can change volume per app and all that good stuff, and try to see if there's some dropdown that lets you pick between Headset and Headphone, and all that.
Second thing: The actual default behaviour seems to be to use the profile that was used last time. But for me, whenever MS Teams is running, it decides that the correct thing is to switch it to Headset mode, because Microsoft knows what you want better than you do, and you want the option that produces shitty sound quality, but bidirectional audio.
Hmm. The issues that come to mind are annoying pairing (Arch -- probably my fault, too manual) and some weird random disconnects on Ubuntu, but that might be some power-saving issue specific to my chip. So maybe I just got unlucky random outcomes.