You're right that it's a difficult balance. I would try starting with a landing page regardless. You can get a list of people interested in the service, by ma

You're right that it's a difficult balance. I would try starting with a landing page regardless. You can get a list of people interested in the service, by making vague promises about the kinds of businesses that will be using it. Then, after you have a sizable list, you approach targetted companies with a list saying "I have 1.6M+ customers interested in my service. That's X% of the market for your service type. I am willing to offer you [HUGE DISCOUNT HERE] to sign up for the service." I'd even offer it free to begin with, until you have x number of users. You're selling the interest in the product to get the business interest. Then you can launch with a list of businesses and you might have a greater chance.