I can't recommend a particular provider, but what I would recommend is that you go for one that does a reseller package. That gives you so much greater scope for other things...
On your specific requirements...
Some hosting companies provide a package called "fantastico", which includes all the cgi & php goodness you'd ever want, including three different e-commerce options.
I'd out-source the credit card stuff to someone like worldpay, which is supported by quite a few of the popular e-commerce systems.
Let me know if you find somewhere good...
