Wow cool, I've been wanting to run a more true Linux based phone. What country and carrier are you using?
The device list covers lots of stuff you can buy cheaply used (upgrade a Galaxy S4 to Android 9, for instance) as well as high-end new devices: https://wiki.lineageos.org/devices/