2checkout.com is popular for international orders also.

Offering multiple methods of payment is nice, and PayPal is so recognized, you'll likely get a few paypal signups with subscriptions too.

When you say that they charge a hefty fee, what fee are you referring to? A setup fee? Or a processing fee?

I've got a place I use that charges reasonable rates for online sales, and if you want to process offline transactions on a machine, they'll send you a machine for free to do that too.

Send me a PM if you need more information on that.