Spot Mobile is technically a T-Mobile carrier now. They highly recommend a carrier unlocked handset, but it's theoretically possible that you wouldn't need to carrier unlock your current phone to use them so long as you don't mind losing MMS/internet access (similar circumstances with P'tel as another T-Mo MVNO). No promises, though, as they used to be an AT&T MVNO and you couldn't use their SIM cards with carrier locked AT&T handsets like you can at Airvoice. Incidentally, if you're happy with T-Mo prepaid coverage, P'tel or Spot would probably be your two best options depending on usage numbers. You might also call up and ask T-Mo customer support if they might be willing to carrier unlock the handset. Never hurts to ask.
As for what to look for, GSM 850/1900 is the magic terminology for feature phone band support in this country, AT&T or T-Mobile GSM service.
There's always
GSM Arena's search tool, but I'm not sure you'll really need it. I've got a small assortment of feature phones listed at the Shopping Hut on my website, but I won't bother linking them. Your best bang for the money and build quality if you can't use the phone you currently have is probably the Nokia 2330C-2B, new and carrier unlocked for under $50 through Amazon. The AT&T locked GoPhone version of this can be had for under $10, but you'll never be able to use it with another carrier besides AT&T, Airvoice, or another AT&T based MVNO. If you're planning to invest money in a good handset again, get one that you can take to wherever you like.