[takd]

I have been using /e/OS on a Fairphone 3 for several months now, and I am quite satisfied.

Yes, it is built on LineageOS, though I am not sure how closely it is tracked.

They have their own cloud services, but you can opt out. You can use your own Nextcloud server as well, which I think is pretty neat: you can have a convenient cloud-based experience (contact and calendar sync etc.) with the stock /e/OS installation, while also having ownership of your data in your Nextcloud instance. (Their own servers are also heavily based on Nextcloud.)

Regarding app stores: I think it is the weakest point. F-Droid is nice but not enough, the /e/OS App Store is a bit murky for me; for most of the non-FOSS apps I use the Aurora Store, which seems trustworthy to me so far.