Your recently unlocked ATT XS and XS max phones are probably GSM phones. T Mobile is a GSM network, so your phones would definitely work on TMobile (may want to take a look at Mint--much cheaper than ATT or straight up TMobile and uses the TMobile network). Verizon is a CDMA network. That being said, the GSM/CDMA distinction is important for 2G and 3G functionality. I think 4G and now 5G are independent of GSM/CDMA, so your GSM phones will probably work on Verizon.
I went from ATT to Mint, and have noticed that there are a few more dead spots with the TMobile network than ATT, but overall am happy with coverage.