I have shared hosting with both of these companies. I've been with Hostwinds for about 4 years, and with StableHost for about 2 years. I also have an account with HostGator as well, so I know where you are coming from.
Early on Hostwinds did have some problems, but they really seemed to have turned things around and I haven't had any issues with them for awhile now. Anytime I had a problem they took care of me. Their customer support was always extremely helpful.
StableHost has been really good to me as well. They have also been extremely reliable.
They are both solid companies. I guess the main question I would ask you is how many domains to you plan to host?
I have Ultimate package with Hostwinds, and recently upgraded my StableHost from "Basic" to the "Stable" package.
The major difference between the two is that Hostwinds has unlimited disk space, where as the Basic with StableHost only had 1GB and I found myself often almost running out space. But then I am hosting several sites hosted their as well. This is why I upgraded my StableHost.
One other thing I like with Hostwinds is that if you buy your domains through them(I think they use Internet.Bs as a registar) you get the option of getting free ID protection(WHOIS Privacy).
One thing that I really like about StableHost is their R1 Soft backups. Which is pretty important for me.
Take all these things into consideration when deciding. If you go with Hostwinds make sure you make your own backups. Will anything happen? Maybe... Maybe Not... But you never know. Just keep that in mind.
It truly sucks to lose years worth of work, and not have a backup and have to restart a site from scratch(I know from experience)..Live and Learn.
I hope this information helps you. They are both solid companies which both have some pros and cons.