I have been very happy with the Galaxy S4, so I'd probably get the S5 in your situation. It's pretty great for the cost as far as Android devices go. If you want to jailbreak/modify your phone, it's probably the best option for that.
Before this, I had an HTC phone. It gave me a lot of problems, but that was at the dawn of 4G, and they may have improved since then. It would frequently reset with no warning or eat battery life for no reason.
My wife uses the LG series, which she is happy with, but beware that they don't have external sdcard capability, so if you intended to store a lot of music or something (like me) it's not the best option. If you have unlimited data, you can use cloud storage though. Another difference is that those phones have their buttons on the back instead of the bottom, which I can't personally get behind.
If you are an Apple person you'd probably prefer getting the iphone, I guess. There are also more games and apps to choose on the apple store (though Android has improved in that regard).
Specifically Dominion related, there is a great randomizer (Dominion Shuffle) that you can get for free on Android. Woohoo.
No matter what you get, just know there will be a learning curve and you may not care for the thing at first. Once you learn the ins and outs, it's hard to go back to an old school phone, though.