I had some other ideas to differentiate, which were a bit of a gray-area hack. This included pulling from the same data sources that Spokeo and similar services use to be able to search for that data. That way, the user wouldn't have to enter any personal information other than say an email address.
You could then offer a free service that let users enter their email address and they would find all the sites you've crawled where you found their information (similar to haveibeenpwned.com), with an upsell to automatically remove it.
Once a subscriber was signed up or previously had used the free service and hadn't opted out, I would keep crawling services for additional data and then give them a warning email when their data popped up again.
It seemed like a semi-reasonable business model at the time, but just a really small market, and I had other business ideas I wanted to pursue.
Also about the market size I imagine the market is just US? It seems other places, at leas Europe anyway has better laws to protect against these kinds of invasive services.
I would be interested in hearing what are you basing this on? Did you do some market research?
My feeling is that there is money in privacy, people seem to have no problem paying 5 or 10 dollars a month for a VPN provider for instance.