I would imagine that most payment gateways would interface well with PHP without any problems.
I would check out http://www.canadamerchantaccounts.com They can provide you with a merchant account at a low cost. All that's needed is a US bank account and they can help you get one of those too. They have a high acceptance rate from what I hear they never turned down anyone yet. Money would be moved from your merchant account right into your US banking account that would be setup for you. I'm sure they can set you up to accept other credit cards like American Express and Discover, if you need to, it will be at an added cost of course.
If you go with a 3rd Party Processor such as http://www.worldpay.com you may have some problems with PHP integration, honestly, I really don't know. But for getting a real merchant account I see no problems at all.