Most of your SIP providers will work with any SIP phone, wired or wireless. VoIP over the internet can still be a pain. Sometimes it works, sometimes it doesn't. That being said, I've used VoIP Street with some success.
Well right now I'm just using a softphone (x-lite). However I've got a Linksys PAP2T on order. You just connect it to your network, configure your voip account settings, plug in an actual phone to it and you're good to go. I've set them up in the past and its a breeze.