I don't see anything illegal here.
Americans are allowed to communicate facts to other people. Any law purporting to limit that ability would have to beat a First Amendment challenge, which is typically a tough thing to do.
With regard to the specific causes of action you mentioned, none of them would apply:
- Privacy: this would not be an intrusion upon seclusion or a public disclosure of private facts, both of which require that the acquisition or dissemination of the plaintiff's information be "highly offensive to the reasonable person." An e-mail address is basic directory information that people freely disclose on a regular basis and often make affirmative efforts to publicize. It would not satisfy that test.
- Harassment: Harassment requires some contact between the defendant and the victim. Giving the service your e-mail address doesn't involve contacting you.
- Spam: Spam also requires that someone send you e-mail. Giving the service your e-mail address doesn't involve sending you an e-mail.
That's obviously all assuming normal use as intended by the service. Other cases could present different scenarios, especially if a user takes your e-mail and uses it to harass you or do something else, those actions would be illegal, but holding the service liable for the user's offenses based on its receipt or disclosure of information would almost certainly fail on First Amendment grounds.
Because the service is legal, there's really no legal reason to prohibit it from advertising on social media. A law prohibiting those advertisements would probably also fail under the First Amendment. Different platforms would of course be free to independently choose not to allow those ads.