Verizon isn't bad if you don't care to splice the minutes up. I don't know how much you and your wife talking on the phone, but I have a plan with very limited minutes per month since I don't do a lot of jibber-jabbering and an unlimited text package, which saves a **** ton of money because that's what I do most of. They're usually pretty reworkable, but I'd get a second or third opinion before diving in.
And I can't tell you anything about good phones. All of my friends have Blackberrys and iPhones and stuff, and I have a grey flip phone with "PHONE" written on the back.