The only shared hosting I've used - after doing lots of research - was ICDSoft :
http://www.icdsoft.com I was very impressed and happy with it for about two years, until I moved to using dedicated servers.
While I had account with them, servers were very fast, always responsive, they weren't overloading the servers (checked with reverse dns, only about 4-500 sites on the server). Support used to answer in 3-10 minutes each time I asked something.
They're not so "popular" (as in you don't see them advertised all over) because:
* you have only 100GB of disk space and 1TB of bandwidth per month (all the cheapskates look for unlimited everything but seriously, when you go over 1TB a month you move to dedicated server or something)
* you can only host ONE main domain per account and a limited number of subdomains (Godaddy and others put hundreds or thousands of websites on a server, lots of IO making reading files from remote hard disks slow etc). This works out in your favor because you know the server that hosts your site won't be overloaded with thousands of sites.
* they also charge in advance for the whole year (but you have 100 day money back guarantee). Basically, another plus compared to Godaddy and others because it removes all those script kiddies and spammers who buy for one month of hosting and then cancel but in the process they screw up the IPs for the whole server.
The customers paying you through paypal or credit cards has nothing to do with the company giving you hosting.
Go to paypal, set up a business account and go from there.
The hosting company has some scripts like Wordpress or eCommerce suites, you can install with a few clicks and then configure Paypal in them if you wish, or you can setup independently a Magento shop (and set paypal to work with it) or whatever other commerce system you wish.