For making the actual charges, a merchant account from an ISO, currently Vantage Card [1]. I pay interchange plus (0.04% + $0.10) per transaction. That's the fee charged by Visa/MasterCard to the processor, plus four hundredths of a percent and a dime. For about a quarter of my volume which are debit/check cards used as credit, that's just 0.09% + $0.31. For the rest, it probably averages around 1.6-2%, far less than the 2.9% flat rate you'll get offered by flashy payment startups.
I use Authorize.net as a payment gateway for that account [2]. If you do look at merchant account providers, they'll typically set you up with a gateway, you don't need to choose and sign up for one yourself. Just watch that they don't use it as a way to add on more than nominal fees.
To actually hook everything up to my websites, I use Spreedly [3]. They're the best thing to happen to payments in years. Spreedly is a single API for 66 different gateways and payment providers, meaning you code against Spreedly and can switch payment companies any time you want without changing any code. They're also a PCI Level 1 Certified card vault for storing payment information to charge again in the future, for e.g. running a SaaS business.
They offer a pass-thru option where you point the payment form on your website to their URL, and they return the visitor to your page with a token attached that you can then use via their API to make charges, meaning no cardholder data ever touches your servers. That means no on-site PCI audits or any of the other nasty stuff required if you store cards yourself.
1: http://www.vantagecard.com/
2: http://www.authorize.net/
3: https://spreedly.com/