Ah you mentioned the HIBP example, although for this search space you may be able to get by with just a download of all of them. If you stick to, say, state by state sharding, you get around 30 MB of hashes for the worst case (NYC).

If you further reduce that by only providing new confirmed hashes since a timestamp, the client can track when they last downloaded the data and pull only the delta, you end up with a few MB a day, which compares quite well to say, a video call.