I own a Pixel 6 and I have bluetooth issues as well. The Jabra evolve headset works fine all the time. JBL earbuds do not work at all. They get listed and you can pair them but they do never connect as audio devices. No error message.
I vave a Kenwood car radio and it autoconnects 2 out of 3 times. Sometimes it connects bluetooth as well but doesn't connect audio. I mean if you swish from top you see that the radio is connected. But if you tap on it it tells you connection not possible after a while. Switching the radio source to DAB and back to bluetooth resolves the issue.
I am unwilling to test all this with different phones and OSs. So I cannot tell if it is related to GrapheneOS. But it's not that GrapheneOS would never work with bluetooth devices.