I just set up Braintree and it was very easy. Probably not as easy as PayPal + Spreedly, though. If you want to go with a "real" payment gateway, I highly recommend it.

If anything, using Braintree removed all sorts of restrictions. They keep all the credit card information. Let them worry about PCI Compliance, not me.