What you mean by "unreliable web hosting". Websites are slow? They are going down frequently?
Anyway, my experience is that you should have moved to dedicated 100 thousand users ago. It does make a difference, not only to users, but to search engines as well. The search engine bots are able to spider more pages and more easily, with less errors - what means more organic traffic for you.
However, you also need to think backup and fail over.