For me the 5 things from top to bottom are the following.
1. Honesty is everything. I been to a TONS of providers who says "24/7" support and doesn't even offer close to it and some that have so called "promised" response times don't offer close to that. Just tell me what you offering and offer all of those things and I will be good.
2. Good communication, a provider that doesn't say what is going on is not good for any business. Or if they are like working on a ticket they should let me know what going on if it goes non responded for hours than they said they are working on it.
3. Reliability, their hardware and network should on quality components to prevent down time from them failing all of the times. I was once at a company that had "HA" cloud yet even though their hardware was operational at all times, their networking and carriers were not even close to so called "HA".
4. Supportive, you may not believe this but some providers were "setting me up for failure". I means like they were not willing to work with me on issues nor even downgrading and even a few problem ones regarding upgrading certain things. You should be with you customers within "good and bad" times.
5. Finally pricing, if a provider provides all the above very well then I would be more than willing to pay a slight premium. But often times most VPS providers just charge way too much for the RAM alone. I would prefer to pay decently for like those instances for each part of the VPS (bandwidth, throughout, cores, diskspace, and the RAM) and not just RAM+CPU+throughout all "mashed up" together.