Welcome to the forums moxy!
There are no guarantees that a VPS will solve your problems, as it would seem that:
a) the server you are currently on is overcrowed. This could happen with a VPS provider depending on what their client to server ratios are.
b) your scripts are not properly optimized, meaning that wherever you take them, they are going to bog down the system.
The best route, I think, would be to ensure that your scripts are optimized as efficiently as possible first. You can also ask your current host if they have any sort of caching system in place for PHP/mySQL queries. This will slow down the number of queries to your DB and therefore, less strain on the system.
Test that out for a few weeks. If you still run into problems, I would suggest going with a semi-dedicated plan. Basically, they are shared hosting plans with very few clients to a server. You won't have to worry about server management either.
Of course, these are just my opinions. I'm sure you'll get a few

Best of luck.