If you want to go cheap, go with Host Koala. I think they are like $5 a year. You won't get an SSL but you can use cloudflare for the SSL for free. I have a few sites on host Koala and it's been as good as hosts I pay more per month than I do for a whole year with Host Koala. If you start getting a lot of traffic and making money, then you may want to go with a better host like siteground. When you decide to upgrade they will move your site for you.
As far as the domain, I always pick a new one that is brandable. It's nearly impossible to find an expired domain that is brandable and not have a bad history. You can see what a site was before at archive.org