I'm currently using shared hosting and most of my Wordpress sites seem very slow. I am looking at changing servers (buying a VPS). Do you think the server change (location change, IP change) will do me harm, SEO-wise?
It can hurt if you do wrong. How to change hosts without any Google probems is to make sure the changeover is fast and happens everywhere all at once in the eyes of G. So go to the new host and set the new nameservers to point to the current site on the old host. Set the TTL as low as allowed like 300 or 600. Then you can change the DNS to point to the new nameservers and wait a couple days. This way it doesn't matter if there is choppy DNS propagation since both sets of nameservers point to the same place anyhow. After 2 days and after everything is moved and ready, then change the new nameservers to point to the new location and put the TTL back like it was.
Don't forget to make sure everything on the site is identical. If you use the domain for mail pay attention to the mx records/accounts when you change the nameservers.
Some hosts just don't know how to serve up WordPress. Buying a VPS is great if it's within your budget, but it may not be necessary. Look around for someone who specializes in WordPress. I get some crazy traffic spikes, and it took me five tries to get a host that worked for me, but I finally did.
Also make sure you have the right wordpress plugins and theme. They can help speed things up.
What are the right plugins? There are too many good options to name. Make sure your plugins are not redundant (like generating duplicate meta tags). Also look at the caching plugins. As for themes look at how much code is needed to generate your appearance, you can sometimes trim a bunch of code (making the pages faster) and still have a good look.