You can also start with a VPS (virtual private server). Then move on to a Dedicated plan. It is better if you keep with one hosting company. All the data will take very long to transfer, instead you can just upgrade plan. You will need a lot of disk space and at least 10 - 100mbps upstream to compete with rapidshare and megaupload. Space is very expensive, so be ready to pay a fortune.
If you use shared hosting, first of all the bandwidth usage on you plan will be ver low and slow. Dedicated Hosting is for websites that need lots of bandwith and only for one purpose. For later you definitely need unmetered bandwidth. Try googling it. Trust me, dedicated servers cost quite a lot of money!
Easyspeedy is quite well known for their good value for quality ratio. If I needed a dedicated server I would either try easyspeedy or fdc.
I would say you need a strong server as the "main server" with perhaps 2GB memory and then all the other servers you add to the server cluster can be with a weaker cpu and 1GB of memory. Don't forget to add plenty of harddrive space!