AFAIK, if you're going to switch to TMO using their new plans to reimburse ETFs, you have to turn in your old phone and buy a new phone from them directly. I don't think you can BYOD with a Play Store phone? So, assuming the N5s from TMO/Play are using the same bands, you should be able to take directly to AT&T with only a SIM switch. And IF you're ok with only 16GBs of storage. As a few others have said, TMO only sells the 16GB model. Seems stupid to me, but whatever.
If you have grandfathered Verizon unlimited data, selling it on Ebay through an "Assumption of Liability" is the way to go. I just made $350 on my wife and my lines instead of paying $250+ in ETF. It was really easy to do. There's a thread on rootzwiki on how to do it. Search on "Sell Verizon Contract and Keep your Number"