We used the HST WFPC2 to obtain I-band images of the centers of 81 brightest cluster galaxies (BCGs), drawn from a volume-limited sample of nearby BCGs. The images show a rich variety of morphological features, including multiple or double nuclei, dust, stellar disks, point source nuclei, and central surface brightness depressions. High resolution surface brightness profiles could be inferred for 60 galaxies. Of those, 88% have well-resolved cores. Twelve percent of the BCG sample lacks a well-resolved core; all but one of these BCGs have ``power-law profiles. Some of these galaxies have higher luminosities than any power-law galaxy identified by Faber et al. (1997), and have physical upper limits on the break radius well below the values observed for core galaxies of the same luminosity. These results support the idea that the central structure of early-type galaxies is bimodal in its physical properties, but also suggest that there exist high luminosity galaxies with power-law profiles (or unusually small cores). The BCGs in the latter category tend to fall at the low end of the BCG luminosity function and tend to have low values of the quantity alpha (the logarithmic slope of the metric luminosity as a function of radius, at 10 kpc). Since theoretical calculations have shown that the luminosities and alpha values of BCGs grow with time as a result of accretion, this suggests a scenario in which elliptical galaxies evolve from power-law profiles to core profiles through accretion and merging. This is consistent with theoretical scenarios that invoke the formation of massive black hole binaries during merger events (Abridged).