We use Beanstream for our Toronto based company. One nice thing about them is they support something like authorize.net's CIM feature, so you can do recurring billing without having to store CC numbers yourself.

One thing to be aware of, though. It is nigh impossible to get a USD American Express merchant account in Canada. If you plan to charge exclusively in USD, this can be a real problem, as you won't be able to take AmEx. We're soon going to go through the hassle of setting up an account at authorize.net or Braintree so we can take AmEx -- too many of our customers insist on paying either by AmEx or cheque.

For more info about the USD-AmEx-in-Canada problem, see: http://www.freshbooks.com/blog/2008/09/25/freshbooks-now-acc...

Note that it is possible to use a US payment processor for a Canadian company. The two things you need to do are:

a) Get an EIN (we haven't yet done this, but apparently it isn't too difficult, even for foreign corporations)

b) Open a chequing account at a US bank. We've done this using Harris Bank (http://harrisbank.com). Since they are a subsidiary of BMO, they are used to opening accounts for Canadian businesses.