The choice of virtual phone provider is usually a matter of availability of service for the countries you wish to support.
Of course pricing, ease of implementation, and service are a considerations too but until you have a favorite provider it's best to first check who can provide the numbers you need.

Quick Guide
For USA & UK numbers check Twilio and Tropo first. Twilio is easier to setup but Tropo has better customer service.
For all other numbers you might check Twilio & Tropo first but Nexmo can often provide service where the others don't. 
Clickatell is a last resort because of the long setup process and the expensive quarterly standing charge.

Things to consider:
a. can you get the number you want? If your character needs a US number then Twilio & Tropo are the two you'll likely check first but if you need a number in, say, the Netherlands or Germany then your choice could be limited to Nexmo.
b. does the number support SMS and/or voice? Support for voice is more widespread than SMS due to national in-country telecommunications rules and interconnect agreements with the providers. So once you know you can get the number you should check that it supports what you need. You may find that in some countries you can't use the same number for SMS and for voice - you can only get numbers that support one or the other.
c. do you have an international audience? Calls and SMS to international destinations (international = not the country your phone number is registered in) are typically blocked and you must unblock them. With Twilio you can do this via te account settings but with Tropo you'll need to send an email to customer support.
d. costs - what volume of traffic will you have? Twilio & Tropo are about the same on price while Clickatell has a very expensive standing charge. However at certain volumes you may find that the pricing favours one provider more than another.