There is no such thing as free credit card payments so let's start by ruling that out. (Actually it is possible to get free payment processing from Google Checkout if you are a non-profit and jump through a few hoops but that doesn't apply here and is the exception to the rule).
You're going to find that your options are limited and when you do the math that they all work out to be just about the same. I wrote an article that compares popular payment options and a true merchant account and Paypal workout to be about the same (Paypal is cheaper most of the time but not by much). You can compare quotes you get from merchant account providers and Paypal using the calculator included in the article.
Paypal is a great processor. They are fast and efficient and very reliable. The main reason why you hear bad things about them is they are not afraid to freeze an account if they see suspicious activity. Sure, there are some false positives, but most of the time they are able to reduce fraud which benefits everybody. Not to mention once you reach the size of a company like Paypal you are going to see complaints about them no matter what they do. There's no way to make millions of people happy without upsetting someone.
If you are getting quotes with high start up fees from merchant account providers then you need to keep shopping around. There are no hard costs related to setting up an account so if a provider says they have one then tell them, "no thank you". There a lot of merchant account providers out there so if you shop around you will eventually find a good deal. You can compare providers using this rate comparison calculator.
Disclaimer: I wrote the article and calculators
