If you're looking for an low cost, un-managed VPS solution I have been extremely happy with
Hostigation (no affiliation, just a happy customer). They're widely regarded in the VPS world as being one of a handful of value priced, well run companies. I have a couple of VPSes from them (three in Charlotte, one in LAX) and have been extremely pleased with the uptime and service. If you do go with them, though, be sure to go with their Charlotte datacenter. It has far better connectivity (they're co-loed at caro.net in NC) than their LA location which is at QuadraNet.
I will take this opportunity to note that many of your lower priced VPSes (including those from Hostigation) are more or less completely unmanaged. You will be expected to handle any and all Linux administrative duties, from installing Debian/CentOS security updates to installing Webmin/Directmin/CPanel or hand editing your httpd.conf files. It is quite a daunting task, in my opinion, to competently secure a public webserver. For this reason you may want to look for at least a semi-managed provider, someone who has very good support you can lean on if you get in a rut.
It appears that VPS.net is a semi-managed company, so they might be a good fit if you're comfortable with the shell to some extent. This is where my experience in this area ends, as I exclusively have experience with completely unmanaged providers.
Back to shared hosting... I am a current customer of HostGator as well and have not had any problems with them. I used to be a DreamHost customer and was honestly quite pleased, but this was before the precipitous quality drop they seem to have had the past couple of years.