Both Chargify and Spreedly require a payment gateway of some sort, no idea about the others.
I believe Chargify only supports Authorize.net currently, and it looks like Spreedly supports a few more.
Authorize.net is only the payment gateway, so you'll need a merchant account as well. A merchant account with a bank is where you have the transaction fee (flat fee per transaction) and discount rate (percentage per transaction). The payment gateway is a monthly fee on top of that ($10 p/month or so), and then you have the fees for the recurring billing service as well (and any special services they require, for instance Chargify requires the customer management part of the Authorize.net API which is another $20 a month or so).
As far as the merchant account goes, start with this blog post: http://danieltenner.com/posts/0006-how-to-get-a-merchant-acc...