If you can pay all the way upto $300, then you should seriously think about a dedicated server.
However for both, I would recomend HostGator.com, and for more specifically VPS's, then VPS Latch.
If what you are looking for is performance, rather than support (only if your experienced with linux ect) then the best un-managed servers I have used have been RackSRV.
Good luck! :)
EDIT: To answer your last question, if all you are running is a few games and websites, then you probally wont need that much RAM or CPU unless you have a lot of MySQL usage (I mean a lot!). 2GB and 2-2.5Gz will be more than enough.