A more efficient way to add query data to a Map

There's no shortcut to what you're doing, but here's a few probable optimizations you can perform.

Use Three Maps

Maps are much faster than manually searching lists (at least 10 times faster on average), partly because they're internally optimized to be faster than linear search algorithms. However, they do not scale as well as lists do. Maintaining three smaller maps should yield better performance.

Use String.replaceAll

Function calls are technically more expensive than simple regexp patterns, so it makes sense to reduce the number of calls you need to make:

l.Company.toLowerCase().replaceAll('[- ]','')

Use Set.clone() When Possible

If you're still using just one map, do this:

Set<String> comparisonSet = comparisonMap.keySet().clone();

This is faster than constructing a new object and using addAll. If you go with three maps, however, you'll still need to use addAll twice to get all the strings in your master set.

References Are Expensive

Every time you need to use a . to deference something, it's costing you CPU time. I'm not sure when the balance between when to switch between direct references to caching variables (because lines are also expensive), but you might try it out:

for(Lead l...) {
    Id leadId = l.Id;
    // Use leadId for the rest of this block
}

Use Internal String Methods, When Possible

You can replace .replace(' ','') with .deleteWhitespace(); this may or may not be more efficient for the Company field, since you're still left with a need to replace one character (the - character), but it's probably better for the other two fields.