You mentioned exactly the two ROMs I'm currently using. GrapheneOS on my Pixel phone. And LineageOS for microG on my Samsung tablet. I'm really happy with both of them.
I don't use that many proprietary tech so there is little issues for me. My car only has regular old plain bluetooth, so I wouldn't know. And instead of some add-on firewall/dns adblocker solutions, I'm just using the ~~Librewolf~~ Mull browser with the uBlock plugin.
Hmm, if you have a home network anyways... Maybe you can run AdGuard/PiHole there. I've switched to blocky.
I made it listen externally and just configure it in the network settings of my devices to override the automatic DNS server. That way I don't need to install sth like AdAway on all of my laptops and phones, because I have one central instance.
Is there anything else that blocks video ads? I've never found anything except for uBlock which actually works. And I've recently learned that you can enable developer mode in Firefox based browsers on Android and install all the Plugins they don't like you to use on mobile. Like SponsorBlock etc.