No first-hand experience with these guys, but I've heard good things: http://chargify.com. It's free until the 50 customer mark, although you'll still have to mess with a merchant account.
Would you have any recommendations for merchant accounts, or are they all pretty much the same?
It generally takes about 30 days to set up an account with a merchant. you can negotiate with many merchant banks regarding the rate. there isn't one that i know of that's super 'startup friendly', but it's not really that important.
We use http://spreedly.com for recurring billing which is very similar to chargify.
The point of these type of 'middle men' is that they a) keep the CC data and keep you from having to deal with the risks and security concerns of doing so yourself, b) make dealing with recurring billing easier; ie we don't have any 'cron jobs' that run credit card batches every night; c) deal with all the subtleties of prorating the user for upgrading or downgrading a plan mid-month; offering free first month, etc.
We've been using Chargify for a couple of months now and it's great. Just a shame you have to have a Gateway and Merchant account as well!
As for gateways, Braintree is head and shoulders above the rest when it comes to service and their API. 3% is about right, or a little high. For more info on the process and market prices check out Braintree's website. They are quite helpful, but a little on the pricey side.