Google Voice.
It's great for visual voicemail (pretty funny translations sometimes!) and free texting.
Since you are coming from ATT to Verizon you can port your current number to GV and get a new number from Verizon, that way you don't have to give a separate number for texting.
You can do a ton with Google Voice, check it out!