Do virtual private servers yield better uptime than shared hosting?

You are really asking two entirely different questions. Here are the answers I'd give:

Will my VPS's performance be dependent on other VMs on the same physical server?

To some extent, yes, although (unless the admins are incompetent) you will receive at least the performance you pay for. Many VPSes are setup so that you can draw more above your set resources, as long as no one else that has been promised the resources needs them.

As an example, CPU usage is affected by this a lot. If there isn't a lot of load across all of the VPSes, you may be able to get better processor usage than you paid for. But the second that someone else starts to heavily use their processor, you're going to lose performance, because the VPS host has promised them a certain number of cycles, and you were using what was theirs. Your performance will decrease, but not below what you're paying for (again, in the right configuration).

Will a VPS experience fewer downtimes?

This is a harder question to answer. Statistically, I say no. A hosted account is one small piece of a complex puzzle, but (in most cases) the server (or servers, more likely) are administered by one group of people, and those people probably have a uniform set of procedures that is documented. One change affects many, many accounts, so they're (hopefully) very careful about what they do. There is a process, and administration is managed, as opposed to ad hoc.

When you get a VPS, you introduce a new variable to the mix. Namely, you. Not only can physical issues and hypervisor issues cause problems, you yourself can introduce instability. If you've got years of experience administering servers, then this probably isn't an issue, but unless you're confident in your abilities and have the experience to back up that confidence, the end result is that your server is unavailable more than it would be in the hosted example.

Generally speaking, more moving parts raises the likelihood of failure. http://en.wikipedia.org/wiki/Redundancy_(engineering)#Calculating_the_Probability_of_System_Failure

If they are allowing heavy users to cause problems to other shared users at any level then it doesn't say much for them. On the other hand you get what you pay for to some extent and expecting high reliability when you are paying so little is a bit optimistic.

Upgrading may help but really your question is unanswerable because depends entirely on the specific host.

I work for a web hosting company and have made a number of observations over time:

Shared hosting is inherently less reliable that renting a virtual server. The reason for this is that on a shared box you're going to be co-habiting with possibly 1500-2000 other websites. The biggest problem we encounter are badly written scripts that soak up CPU and memory over time. Downtime or poor performance on a shared server can quite often be attributed to just 5% of sites. On shared server all sites on that machine are competing for OS resources.

A dedicated virtual server will be more reliable, the resource competition is not at the OS level but at the hardware level. If your hoster has tuned and properly governed their virtualisation platform then you should rarely see issues. For example, our own platform does not overcommit CPU or Memory on the virtualisation nodes. Also, should a virtualisation node fail, any VM's running on the node are migrated to other nodes and are back up and running within 30-60 seconds.

Whilst a VM will be sharing hardware resources with other VM's on a single machine, the partitioning is such that (in a properly resource managed environment) another customer's VM should never affect the performance of another use.

I won't take a stab at what might be the technical reasons why or why not a VPS might mean less downtime since others have offered insight into that.

To my way of thinking for something like this, the particular flavor of hosting isn't really the key to performance and availability. It's more likely to be related to the services offered and what your agreement guarantees to you.

If you've got no customer-level agreement that guarantees a given measure of performance or availability or, if your downtimes fall within the agreed-upon guarantees, then you're getting what you paid for.

While some providers do seem to imply better service with different backend models, that's not necessarily true and can just be marketing. It's really an issue of what level of service is being purchased and how they guarantee it.

If you need better, you buy it and make sure you get the guaranteed service you think you bought. If it's got the features, functionality, and availability you need at a price you can afford, it is a good value.