This topic is discussed at length on Joel Spolsky's Business of Software (BOS), and there's a few threads dedicated to this topic at the
Scroll to the middle of the page to find the topics on payment processors.
I just signed up with FastSpring as my payment processor, and am very happy with them. It only took a day to convert from PayPal. Fastspring also includes PayPal as a payment option, so I didn't loose PayPal as a payment option for my product.
PayPal has no shortage of bad press online from sellers.
However, as a buyer, PayPal really increases my own propensity to make small / impulse purchases. Good buyer protection, no need to share credit card details, trusted brand, and the fact that my account is already sometimes funded.
I personally think you'd have to offer it, but others may have more detail re effect on your conversion rates.