+1 for Braintree. We have used several different payment providers over the years, including PayPal alone. We switched to Braintree back when they were offering $50K in free payment transactions.

The payment integration was straightforward, and getting built-in support for PayPal (which accounts for 16% of our sales) and the ability to safely vault payment methods made it a no-brainer.