Motivated by the recent, serendipitous discovery of the densest known galaxy, M60-UCD1, we present two initial findings from a follow-up search, using the Sloan Digital Sky Survey, Subaru/Suprime-Cam and Hubble Space Telescope imaging, and SOuthern Astrophysical Research (SOAR)/Goodman spectroscopy. The first object discovered, M59-UCD3, has a similar size to M60-UCD1 (half-light radius of r_h ~ 20 pc) but is 40% more luminous (M_V ~ -14.6), making it the new densest-known galaxy. The second, M85-HCC1, has a size like a typical globular cluster (GC; r_h ~ 1.8 pc) but is much more luminous (M_V ~ -12.5). This hypercompact cluster is by far the densest confirmed free-floating stellar system, and is equivalent to the densest known nuclear star clusters. From spectroscopy, we find that both objects are relatively young (~9 Gyr and ~3 Gyr, respectively), with metal-abundances that resemble those of galaxy centers. Their host galaxies show clear signs of large-scale disturbances, and we conclude that these dense objects are the remnant nuclei of recently accreted galaxies. M59-UCD3 is an ideal target for follow-up with high-resolution imaging and spectroscopy to search for an overweight central supermassive black hole as was discovered in M60-UCD1. These findings also emphasize the potential value of ultra-compact dwarfs and massive GCs as tracers of the assembly histories of galaxies.