We have an Authorize.Net merchant account, use Recurly for subscription billing, and found our merchant bank using FeeFighters (ended up going with Merchant Focus).
It took us less than 2 weeks from start to finish, paid $0 in setup fees, ended up with a transaction discount rate from 1.75% to 3.1% depending on card type (Merchant Focus uses interchange-plus pricing), and we accept all major card types. Not only that, there is no delay or holds placed on our account. We were able to accept paying customers within 2 weeks of setting up our accounts, and we only pay the Recurly monthly fee, a $15 Authorize.Net gateway fee, merchant account transaction fees, and a $7.95 a month Amex fee (their monthly minimum). All in all, I think we ended up doing well and wasting little time.
I'm not sure why it would cost a few hundred dollars and take as many weeks/months as it did in the OP's case. Perhaps because it was a non-US company?