It's got to be easier. Their customers, who will soon be your customers, need to be convinced that your service is easier to use and work with. Make their life easier when they use your service.
Cheaper might win some customers but it's a risky play - your competitor may well jump in and undercut you and then you've got a price war. I'd steer clear of trying to compete on price. Your competitor is probably big enough to swat you.
Use your agile, flexible, lets-just-do-it startup approach to surprise your competitors and get a bunch of features in that they've wanted to for years but haven't got round to it. Look at what they do well and make sure you do it just as well. Find something they don't do well and make sure you do it better.
Get as much feedback from these potential customers as possible and survey them - ask them why they use that service and what they would like to see improved about that service. Then implement the most demanded ideas.
Make sure you are discoverable by your potential customers. There is no point in spending money and time on your service if nobody can find it. Find a way to get in front of your prospective customers. You know your industry so leverage that and start thinking about how you are going to market this great service.