Definitely buy used, whatever phone you decide to get. Swappa is a good site for buying used phones, less risky than trying to buy from Craigslist or eBay.
As for phone plan, I’m happy with Ting since I don’t use my phone much, so it’s cheaper than most other plans for me. But if you need unlimited talk+text+data, there are other companies that offer that for around $25-30 per month.