2Checkout is the way to go, they have good fraud detection too. It's also probably one of the easier gateways to sign up for. Others, like Authorize.net make you jump hurdles to get signed up.
As for paypal, you pretty much need to offer it or you're just throwing away possible new clients.
SolaDrive - Enterprise Managed Solutions
Specializing in Managed SSD VPS & Dedicated Servers in US & UK
Visit us at SolaDrive.com