I'd be looking into phones with alternative Linux-based operating systems, like Tizen and SailfishOS. Android has been getting progressively worse with each new device I've owned, and I just don't think it's worth the money at this point.
Tizen seems to be the most actively developed alternative at the moment, with some of the more recent Samsung devices running it, and it has the bonus of using glibc, so is likely to be much closer to a "standard" Linux distribution than Android. This is handy if you want to be able to SSH into your phone, for instance -- you can do that on Android, but it's annoying to set up and of questionable usefulness without a proper Unix userland.