Android hardware running GNU/Linux distros (such as Sailfish OS) on top of Android blobs via libhybris could be a stopgap solution as well. But indeed, phones running normal Linux distros need to be the norm in this case.

I have Librem pre-ordered but I expect it will be barely usable as an Android replacement (yet). Though it had to start somewhere and I am glad Purism started that. There are many many smaller and bigger things which went into Android or iOS which will need to be re-done from scratch and things like Google Pay probably won't ever be on such a device. Camera will probably be quite bad, etc. On the other hand, there is Andbox which should partly fill in the app gabs in the meantime.