I been on my Galaxy S5 for longer than I have ever been on the Galaxy S (the first one) and Galaxy S3, and I think it's finally time to replace my phone.
Performance wise, my phone is still going quite strong, especially since all I ask out of my phone is MP3 Player, basic phone functionality (Texting, Calling, etc.), so in that regard the phone now is doing me well and I have no need for a top tier $800+ phone, especially looking at the Galaxy S8's strange design that scares me a bit. iPhones are out of the question as well seeing the huge wall garden and what I have to give up to migrate to there, not worth.
But the software is very much outdated I think. So I figured I should migrate to a new phone to get newer software and maybe I can get proper Bluetooth where my Bluetooth headphones aren't causing serious issues for me cause as much as I love 3.5mm Headphones, I like exercising with my phone and music, a wire out of the way would help me in that regard. Hopefully the phone has some water resistance as well on the exterior, that's quite useful for me as well.
I don't plan on spending more than $300 on a phone but spending less than $100 might be a problem as those phones won't do better than my S5 is now most likely even in terms of software.
The S5 is in the list of supported phones. Actually there's several versions, you may have to figure out which ROM you'll need for yours. Based on the "Lineage 14.1" version number, it looks like the S5 gets an Android 7.1 ROM. That would solve the issue of having an outdated OS.
All you need to do (I know, it can be a couple hours of nerve-wracking work) is flash another recovery so you can install the ROM. Considering the S5's popularity, finding a good guide shouldn't be too hard. Most guides will recommend TWRP as a recovery and will usually link to it too.
Think of it this way : the phone is worth almost nothing second-hand and the warranty has expired anyway. what do you have to lose?
Lineage doesn't have all the Google nonsense by default. No Gmail, no Google Now, no Play Store, nothing. There are plenty of alternatives for the Play store if you would want to de-googlify yourself. If you do want the full Google experience however, you can flash the Opengapps package of your choice.
If I'm not mistaken the S5 has a 32bit processor, so that'll be the regular "ARM" option. The "pico" package has the very basic functionality, you can flash that and then install all the Google stuff you want via the Play Store. Or you can choose a package that has it all already. Just keep in mind that if you install a package that has things you'd prefer not to have, you won't be able to uninstall those things without completely re-flashing the entire ROM with a smaller Opengapps package.
Of course flashing your phone will delete all data on it, so make sure you have backups of everything that needs to be backed up (pics, text messages, login credentials, contacts, etc etc etc)
As @anon37371794 noted Lineage is available for the S5. And you can still buy a new S5 if you are experiencing hardware problems.
Some phones now have much faster internal storage and faster higher quality cameras. I moved to a Oneplus 3T for both the wife and myself. They are great and work flawlessly with LineageOS. A little more expensive than your price range but worth it considering they are on par or better than the apple samsungs. Theres also a new one the Oneplus 5 that may reduce the price of the 3T.
I doesn't appear to be available in the North American market but I just got me a mid range Lenovo P2. Seems they're sticking to the Motorola branding over there. The closest I found with some quick googling is the Moto Z Play, though instead of the 5000 mAh battery the Moto "only" gets a 3500.
Anyway, the Lenovo P2 with its low power Snapdragon 625 (8 cores at 2 GHz) proved to be noticeably faster than my LG G3 which uses the same Snapdragon 801 as the Samsung S5. That together with a 5000 mAh battery made it feel like an okay upgrade. Complex websites run a lot smoother and I finally have a phone that can go for three days.
Two weaknesses is a relative lack of protective accessories (no official ones) and the odd choice of not fitting a USB-C connector on the thing.
With a Samsung S5 I would try some alternative firmwares first like CaptainChaos syggested. My LG G3 was too entrenched so I could never get into that: At least this Lenovo P2 boot-ROM is unlockable from within the developer menu, for whenever upgrades eventually dry out.
I would look into the OnePlus 3T. The OnePlus 5 just recently came out, so the OP 3T should drop it's price soon. With the OP3T, you're going to get buttery smooth performance for years to come because of it's software optimization and I can already promise you it's faster than any Galaxy phone that's out right now. Hell, even my old Nexus 6P (a two year old phone) is a far more fluid experience than my S8+.
If you're serious about software, avoid TouchWiz or "SamsungExperience". It really isn't that great compared to stock Android.
I just purchased (not yet received) a Xaomi Note 4x from "gearbest" in Hong Kong. You need to be patient if you order from China it takes about a month to get it.
It was on sale at the time for $125. Even now off-sale it is less than $150. Gets great reviews for a phone of that price so you may want to check it out?
Of course, make sure any phone you buy will work with your carrier. I use "willmyphonework" to make sure the bands are what I need.