With that budget, the world is your oyster really. I'm a huge fan of my LG G3, but it's not unlocked from the get-go, you have to root and install a specific recovery, but once you do that it's totally unlocked. I'm running the latest version of Lollipop on an AOSP based ROM without any problems (except wireless charging, which still doesn't work on LP, nobody can figure out why).
I wouldn't go with the Nexus 5 because that's basically outdated at this point. If you want a Nexus device, get the Nexus 6.
I'd steer away from Galaxy S5 if you want an unlocked device. Samsung/Touchwiz is as locked down as it gets. Nothing against your phone Mandrake, but they aren't the easiest devices to deal with when you're looking for something unlocked.