We use Bank of America. They offer online payroll for $15/month. Free if you pay with direct deposit and all of your employees have BofA accounts. They will prepare and file fedaral and state tax forms and payments as well. That's a very good deal.

We use Quickbooks online (QBOE). Clunky interface. MSIE only. But it's a webapp (don't worry about backups).

We use PayPal for credit cards. They are not "unprofessional" and their API is simpler than any bank or merchant company that I know of.