I used to run my own webhost company so I know something about this, however, VPS is a newer feature though I used VPS scenarios while consulting to a global telecom during this period. So I will be working from this point of view.
A dedicated server and VPS are essentially the same for this discussion. This would give you appropriate control and assure (as much as it can be) that no other person can effect your security negatively.
However, a shared server can be very scary. If you are worried about security, then a shared server should not be used. In fact, for many e-commerce scenarios where a bank and/or insurance company is involved with your efforts, they will require that you do not use a shared server, have a dedicated IP address, and have a certificate that is private.
When I was hosting sites, I restricted certain apps from being installed and had agents that constantly checked sites for banned applications or unknown applications and automatically disabled them. I do not think any webhost is doing this.
On Monday, I found a site on a shared 1&1 server that was a hub for a trojan using port 80. This means that any web browser request to any site on the server, was captured and added to a blacklist. This is not something you want.
As well, even if security for your site is not violated using a shared server, if any site on the server acts badly, then the whole neighborhood (being the servers IP address and possibly the whole IP address class in this case) could negatively effect your site.