Beside the quality, uptime, security etc, probably you need to spend a lot in advertising. It takes a few years for the brand recognition to kick in, though.
Your digital marketing and support team matters a lot in enhancing quality of your hosting.So, invest in some good employees, train them properly and also keep up with the market trends.
Find your niche and go for it, there is so much competition it's important to go for that small niche and then deliver an outstanding service, they will stay with you forever and do the word of mouth recommendation for you
Go latest, by that i mean offer Cloud Hosting as mostly users are concerned about how updated company is with their offerings.. Probably we can't really match prices with Digital Ocean or AWS or Google's but we can atleast start to offer what really users needs at the moment.
If that can't be done then probably offer aggressive prices but don't oversell. Provide niche based VPS, like Pre-Wordpress Installed Ready Blog or Pre installed scripts like node js.. also you may try offering your listing at Google Adwords.
A lot of users are moving to Cloud because of its uptime guarantee, so yes, it is important to offer all latest hosting services.
The Virtualization technology you use on your servers also matters to customers.