The only Linux phone I know of that's actually purchasable for humanly reasonable amounts of money is the PinePhone. Everything else I've seen is yet another Android, and Android is tied to Google.
You're right about the app store, but I don't visit that regularly. OTOH, Google and Amazon have conditioned me to ignore anything that's "promoted" or similar.
App compatibility is good, with some apps not showing notifications without installing Google Play Services (which Graphene allows to run sandboxed like other apps). Ive been running without play services
I've been using SailfishOS on my Sony XA2+ for nearly three years and it's brilliant. Using the licensed version, I can also run Android apps as long as they're not dependent on Google services, although I prefer the UX of the native SailfishOS apps.
Also, it really depends on your threat model; the place where Android and iOS shine is mitigating untrusted apps, but ex. my pinephone doesn't have any untrusted apps, so a lockscreen and at-rest data encryption is fine for the threats I care about[0]. And if you really must run untrusted software, there's always flatpak et al.
[0] Actually, my pinephone isn't a daily driver and doesn't have even enough sensitive material for me to bother with encryption, but that seems a bit much to expect in general.
For all the shit android gets, it does have good security built on top of linux and open-source tools (selinux, every app runs as another user so that the kernel’s built in access control is actually useful, etc)
Yes, if the distro is shipping malware we're going to have trouble. How many times has that happened? For all time, in any distro, ever?