Simple Helix is offering a FREE account for use with Magento, and you cannot beat that.
I run my own dedicated server to host my own clients, and it has full Magento support and a decent control panel, but I don’t market myself as a web host, except to my clients. But if you are interested in someone to design your Magento shop with a fresh look, modern style, and usability-focused design, feel free to give me a shout via pm.
I can vouch for Helping Hand Host. Jeff me up with an account and even did the installation for me (he brought it up, not me) in tip-top time. Of course, Helping Hand Hosting is not void of anything else that shared-hosting does, and slightly slower speeds, etc. is expected and regular. I can say that they seem to be quite courteous and will set you up with 2-months free without asking you to sign-up to a prior commitment.. A genuine trial!
Hello, I would avise you to try 3ix : http://www.3ix.org/sys/aff.php?aff=3387. I’ve been using it for quite a while and their service is really good. If you even need to enable a PHP extension that’s not in the default hosting they will do it for you within a very reasonable delay and at no cost. The data storage is huge (shared with the DB so that you have enough space for your DB). The SSL shared certificate is FREE. And the price is the lowest I have found. I was previously on 1and1 but since their prices have increased they are no longer competitive.
I am sure that many Hosting companies will do a great job.
I have chosen simplehelix (just now testing magento at $ 4.95 a month).
They have given me superiour service (they offered to do the magento installation for free, as it did not work out for me). They have responded quickly to any inquireries. They offer many one-click installers (such as WordPress and Drupal), and will even put up new one when asked.
So at least, you should be well served with them. Good luck!