if the hosting uptime is good, it will not effect seo . that only effect your site speed. it's related with your users
With dedicated hosting you get a server to yourself. Its better for SEO since you won't have any banned sites sharing your ip.
dedicated is preferred. your Servers downtime should be minimized. 301 redirect of yourdomain.com, www.yourdoman.com & http://www.yourdomain.com to http://www.yourdomain.com
Another important factor when considering to use shared or dedicated services is the actual IP address. You shouldn't have a problem with dedicated services, as you usually get an unique IP that hasnt been used before. However on shared hosts, you never know what the other websites on the server are doing. They could be spam sites etc. The search engines have said this doesn't matter in their result indexing, but it is always better to be safe then sorry.
Or worse because if your doing anything "shady" all your sites are alone on the same box no one else but you...