I just took a plan with US Mobile, which does AT&T, T-Mobile, and Verizon - basically an independent. They were very flexible and helpful, and the price is low (perfect for a dumb phone). There was never any question as to whether the phone was supported - got the physical SIM card and it just worked. My first ever cell phone, and pretty easy to get started.
No affiliation with US Mobile.