We need Linux OSes and phones to catch up to really break free from this duopoly. Only when there is enough traction, essential infrastructure like banks will start supporting Oses like that. It's a chicken and egg kind of problem.
Why start from scratch?
I've been on ubports for 3 years and while it also has some weird caveats like read only rootfs, no working package manager (due to read-only fs. however ubports has pretty cool support for lxc containers where you can use apt). Due to chronic lack of time I haven't been able to sit down on my phone to play with it a bit (for example id like to install waydroid), but it seems a lot easier than android. For example, while there isn't an app for call recording, some guy worked around it by writing a systemd user service as a workaround[1]. This is exactly the type of thing I'm thinking about when talking "linux phone".
For me as a linux user, the difference if ubports was a human, I'd think that perhaps they were sick, whereas if android was a human, i'd shoot them in the face :)
If your goal is security and privacy (which go hand in hand), mobile OSes are clearly the best solution.
Anyway Android is still a Linux OS. The only requirement to be a Linux OS technically is to ship a Linux kernel. Adhering to freedesktop specifications like the FHS, using systemd, using GNU userspace software, etc. isn't necessary.
On Android you can install software by installing directly from APK files or you can use application stores which are package manager, they help you install software and if there are dependencies they can also install the dependencies if they support that.
Call recording is possible on multiple Android OSes, it's possible on stock PixelOS and GrapheneOS, I'm not sure about others but normally it's just part of the Dialer app. You don't need root at all for that.
Remember that GrapheneOS is not Android: it's an AOSP-based OS.
I actually had hopes that Huawei would start that with HarmonyOS.
It is finnish, anyone knows how are they going?
i used that for 2 years, it's linux+kde bottom to top, a terminal + shell is a builtin, though only supporting 5+ years old Sony phones got tiresome.
Still.. it seems the only one that's usable enough apart of the duopoly. May have to switch to it again.
The situation with Sony Xperia devices is not great, the best experience is still on the X10III (from 2021 I think) and there are significant issues with the support of 10 IV and V generation devices (a free beta release is available for those as well).
It seems that recently there has been quite a lot of buzz in the Sailfish community compared to the past few years. In the public repos there are some interesting contributions like xdg-shell support for Lipstick, which looks set to enable compiling many previously unavailable Linux apps natively if that will actually be integrated in an upcoming OS version.
You can run desktop apps on GrapheneOS including on a desktop monitor via the desktop mode with free form windows. There's support for non-native apps via hardware-based virtualization. These features are experimental but already work pretty well.