These services were just the natural extension of the phonebook. At the exact same time as the phonebooks stopped being circulated, these services popped up online.

And since everyone's name, address and phone number was in the phone book (At least for their city) people didn't find it weird when it popped up online. Sure, to do the same thing for the whole country you'd need dozens of phonebooks for different areas, but it was just the same information.

Which makes me wonder: weren't there phonebooks in US cities and in other countries before? Were they incomplete/opt-in?

The key thing about the Swedish phonebooks were that they were opt-out, so people were basically all in the phone book. So even before the internet, it was just very natural that your name, address and phone number was public. "Getting someone's number" as in moves and TV wasn't a thing. You could just call anyone if you knew their name.