NMI would be my first choice, followed by eprocessing network (EPN). Both are cheap compared to authnet, payflo, or most others. They offer recurring billing, customer storage vaults and just about any other feature you would want. These would require a merchant account to use the payment gateway. 2CheckOut and Paypal are 3rd party processors and not payment gateways. I would also absolutely accept Paypal as an alternative payment method. It's so widely expected for online purchases that it is almost essential as a second payment option.
Full disclosure, we private label NMI and work with or resell EPN, Payflo, authnet and about 10 others regularly. We use NMI for our own merchant account, and I would continue to use them based on their price, features, and support regardless of any other factor.