Thank you for the PM's and the link...
I find it difficult to really discern any significant differences between all of the hosting companies out there. Do a search and visit different "host rating" sites and you get varied results. I really need to stay within a budget and shared hosting offers many cheap options but I am afraid that going from what I have now to a different shared environment will give me the same problems. From what I read around here a VPS plan might be worthwhile but again, plans vary and so do costs.
Does anyone use or have used Go-Daddy? They have some affordable Linux VPS plans. Personally, I think there is no way to tell what your experience is going to be and I guess I am going to have to just go and do and see what happens.