Graphene is technically more secure than Lineage, because you can re-lock the bootloader.
But wait, the latest versions of Lineage you can re-lock the bootloader on Pixel devices (or is it with DivestOS, a Lineage fork, on Pixels? I forget). Either way, both can be re-locked on Pixel (I know, I’ve done it).
At that point there’s little difference in my opinion, if you aren’t using any kind of Google services.
Once you go to use Google services (either sandboxed on Graphene, or microG on Lineage), it can be argued that Graphene is more secure. Though Lineage and Divest install microG as user apps, so you could install them to a second profile and isolate it there.
But if you’re going to run some form of Google services, you’re kind of negating the advantages of Graphene at that point (though some would argue it’s still more secure, again, depending on your threat model - if a state actor is after you, don’t go putting Google stuff on your phone).
Really it all comes down to your threat model. I’m currently running DivestOS on a Pixel with microG, because there were a few apps I still needed. My next reset (in about 3 months) that will be gone, and I’ll no longer need anything Google. But I’ll probably stick with DivestOS, as there’s no clear advantage for me to switch to Graphene.
My experience: most of my apps work fine without Google services. Even more advanced apps - sometimes they just can’t verify licensing, so may complain occasionally. Even now, Macrodroid can’t verify licensing through microG, but the dev has a process for licensing with a serial key based on your Google account.