If he can wait until October, there's new versions coming out of some great phones. Since he's already invested in the iOS ecosystem though, it may make more sense to just go to the iPhone 5.
As a Verizon customer, he won't be able to do both data and voice simultaneously. Leo says that isn't the problem of the iPhone, it's the problem of Verizon's network. The only way that Samsung's Galaxy SIII can do it is because it has three antennas - two LTE and one CDMA. Leo also says that if he travels internationally, getting a GSM "Burner" phone is probably easier.
He won't be disappointed with a Galaxy S III, though, and won't take too big of a hit replacing his iOS apps with Android ones. They are inexpensive.