We present deep, high angular-resolution HST NICMOS imaging in the Hubble Deep Field South (HDF-S), focusing on a subset of 14 distant red galaxies (DRGs) at z~2.5 that have been preselected to have J-K>2.3. We find a clear trend between the rest-frame optical sizes of these sources and their luminosity-weighted stellar ages as inferred from their broadband spectral energy distributions (SEDs). Galaxies whose SEDs are consistent with being dusty and actively star-forming generally show extended morphologies in the NICMOS images (re>~2 kpc), while the five sources that are not vigorously forming stars are extremely compact (re<~1 kpc). This trend suggests a direct link between the mean ages of the stars and the size and density of the galaxies and supports the conjecture that early events quench star formation and leave compact remnants. Furthermore, the compact galaxies have stellar surface mass densities that exceed those of local galaxies by more than an order of magnitude. The existence of such massive dense galaxies presents a problem for models of early-type galaxy formation and evolution. Larger samples of DRGs and higher spatial resolution imaging will allow us to determine the universality of the results presented here for a small sample. Based on observations with the NASA/ESA Hubble Space Telescope, obtained at the Space Telescope Science Institute, which is operated by the Association of Universities for Research in Astronomy, Inc., under NASA contract NAS 5-26555. These observations are associated with program 9723.