Maybe start with GrapheneOS on a Google Pixel phone, its a privacy/security focused Android fork.

Otherwise for full Linux, take a look at shipping-with-Android devices that are semi-supported by postmarketOS, Mobian etc. Or go with vendors focused on non-Android Linux like Pine64 PinePhone, Purism Librem, Furilabs, Liberux and maybe some I forgot. The Debian Mobile wiki page has a whole lot of other links but I stopped maintaining it.

https://pine64.org/devices/pinephone/ https://puri.sm/products/librem-5/ https://furilabs.com/ https://liberux.net/ https://wiki.debian.org/Mobile

May I add this link to your interesting list : https://volla.online/en/

Volla OS looks like an Android fork, so more like GrapheneOS than postmarketOS/etc.

When buying the phone you can choose to have it with Ubuntu Touch instead of Volla OS. There is also multi-boot.

Ubuntu Touch is still an Android-based OS (they used to have a variant that didn't rely on Android, but discontinued it).

Thanks for that precision, I didn't know about that fact. For those interested : https://wiki.ubuntu.com/Touch/ContainerArchitecture

Smartphone Linux is a total mess. Even postmarketOS does not have a single fully supported and maintained device it can point to and say "buy this, you can run fully featured Linux on it". Very sad. The best option seems to be running Termux on GrapheneOS on the latest Pixels.