can any of you tell me some of the very high quality hosts who have been around for while?

This is going to be quite subjective. What is it that you really want/need and maybe someone can get you going in the right direction...

i guess just a company who already has a name for themselves. I'm sick of having changing hosts ever month :(

Some companies have reputations depending on your needs.
Some are better at pricing. Some are better at service.
It really depends on what you need from them.
The more specific you can be; the better. ;)

Moreliator, regarless of who is recomended, make sure they accept UBB being that is what you are using as some host do not.