For generic mesoscopic systems, such as quantum dots or nanoparticles, we study the Anderson orthogonality catastrophe (AOC) and Fermi-edge singularities in photoabsorption spectra in a series of two papers. In the present paper we focus on AOC for a finite number of particles in discrete energy levels where, in contrast to the bulk situation, AOC is not complete. Moreover, fluctuations characteristic for mesoscopic systems lead to a broad distribution of AOC ground-state overlaps. The fluctuations originate dominantly in the levels around the Fermi energy, and we derive an analytic expression for the probability distribution of AOC overlaps in the limit of strong perturbations. We address the formation of a bound state and its importance for symmetries between the overlap distributions for attractive and repulsive potentials. Our results are based on a random matrix model for the chaotic conduction electrons that are subject to a rank-one perturbation corresponding, for example, to the localized core hole generated in the photoabsorption process.