Most hosting companies don't charge you extra for SSL except for perhaps an initial setup fee to generate then install the cert. So if Yahoo wants more money for that "luxury" dump them quick.
I have my own dedicated server, so I'm not the best to ask. But I only host stores that I manage, not for just anybody. This way I retain complete control over what is loaded.
I've heard lots of people praise BlueHost. I'm sure Google will find it for you. Good luck!