-Get with a provider who has a good reputation for honesty, and won't aggressively sell you on deceptive rates. More often than not, the rates you're looking at when talking to a sales rep are not the rates you'll actually be charged. Discount rates, Misuse of Auth fees, NABU fees, APF fees, etc. are all easy for a provider to mask and confuse new merchants with.
-Get with a provider who has a reputation for excellent support. You'll have questions, to be sure. Collecting money from your customers is the most important part of your business; Make no doubt about it.
-Get with a provider who has a good strategy for dealing with PCI compliance. If you're storing cards in your database, or even just passing secure data through your server, PCI can be a very significant burden.
-Get with a provider who can get you up and running quickly. The more time you spend researching this decision, the more time you're not selling. The underwriting process is not likely to differ much between providers (with the exception of PayPal, who seems to do their underwriting after the fact - but that's an entirely different and frightening subject), but there are some truly frightening APIs out there, and a couple very good ones.
The process you describe is what many merchants do. They validate the card info when the user signs up / orders the product, and charge when it ships. Any gateway should be able to support this model, some do it more elegantly and intuitively than others.
This is right in my wheelhouse - I work in the industry. Stick to the above points, and you should be okay.