That's easy: use checking accounts. They are essentially free. That's why PayPal pushes their users towards them. Credit cards are the expensive ones.

But the most effective way to reduce the percentage overhead is to make the transaction bigger. That's why Tipjoy's aggregation of payments is good: pay $1 in 100 different places, and your overhead for a credit card will be around 2.5% vs. 20% for a single $1 transaction.

You can also negotiate to lower the overhead, and to my knowledge, that takes large usage more than it takes money. iTunes for example has 65M credit cards. They do whatever they want.

Well, clearly you have figured it all out :)