We recently switched to Braintree from PayPal Payments Pro. While we're not "small," (>£10million/year) the process was largely painless and I can't recommend them enough. We also needed to take AMEX cards and found setting that account up extremely easy (though we already had an AMEX account).

The only thing that does seem slightly annoying is all their support and accounts people are in Chicago, meaning the inevitable back-and-forth can drag on for way longer than it should for merchants based in Europe. Hopefully this is something they will get ironed out once they have some significant traction in the EU.