Doesn't quantum collapse or decoherence mean that information is being lost all the time? So why is the loss of information in black holes such a big deal?
Decoherence does not mean that information is lost - it just 'degrades', like it would happen in a big classical system with the increase of entropy. But the information is still there.
Quantum collapse is another matter. Yes, if quantum collapse was an objective non-unitary process, then it would imply the loss of information. I believe there's even been some hypotheses about collapse being caused by gravitation, which would link the two phenomena. In general, they're not associated. I imagine part of it is that people tend to assume that the collapse must have some kind of explanation and don't focus much on it as a mystery the way they do with black holes. I think we may actually be missing something there.