"I tried replacing Android with Lineage OS on a old phone I had. Whilst that meant I didn’t have any Google Apps on my device, it was still Android underneath. Also many apps kept complaining that I didn’t have Google services on the device."
An alternative is to install microG [1], which reimplements assorted Google services. YMMV, but I've been able to run ~70% of all Android apps with no problems.