Opting out of ATT seems like the most obvious no-brainer, but are there options for phone service that are actually halfway decent?
Or as an alternative, would it be feasible to get some kind of internet phone/texting service, use that over wifi, or maybe have a basic data plan to go with it at most?
no such thing. just go for the cheapest. buy an rfid case when you are not using wireless networks, to avoid triangulation. Or buy a Fairphone/Librem 5/Shift6mq/PinePhone, those have hardware buttons to disable data receivers, but they cost a lot more than any other smartphone, but shouldn’t be a problem if you can afford Samsung or Apple