Shared hosting is bad for small sites. The downsides is, you are sharing resources with other people you don't know. This can load to server instability and security issues.
The time is to move is when
- you are ready to address the above concerns
- you need to do more outside a basic LAMP Stack
- you have the money to afford a nicer hosting solution
It's kind of a judgement thing, and there isn't a set number. You just have to way the Pro's and Con's versus the cost of a more robust hosting strategy. Shared Hosting might still be for you, just maybe with a more reliable vendor.
Using VPS / Cloud gives you more control/protection over security and shared tenant using all the resources, but are still subject to some edge cases.
Some options are Amazon's AWS, VPS.net, Rackspace and Linode. Both Rackspace and VPS.Net have shared hosting plans so you can slowly move into a more robust hosting setup. These 4 providers are really cream-of-the-crop IMO and I'd recommend them any day of the week.
If you are more paranoid about security, there is another good on called Firehost.
Dedicated hosting is another option, Rackspace provides this, as do most CoLocation and Datacenters. This is really quite large, But with all the VPS providers I haven't had a need to look into this in a while