We present HST NICMOS+ACS and Spitzer IRAC+MIPS observations of 41 galaxies at 2<z<3.5 in the FIRES MS1054 field with red and blue rest-frame optical colors. About half of the galaxies are very compact (effective radii r_e < 1 kpc) at rest-frame optical wavelengths, the others are extended (1< r_e < 10 kpc). For reference, 1 kpc corresponds to 0.12 arcsec at z=2.5 in the adopted cosmology. We separate actively star forming galaxies from quiescent galaxies by modeling their rest-frame UV-NIR SEDs. The star forming galaxies span the full range of sizes, while the quiescent galaxies all have r_e<2kpc. In the redshift range where MIPS 24 micron imaging is a sensitive probe of re-radiated dust emission (z<2.5), the 24 micron fluxes confirm that the light of the small quiescent galaxies is dominated by old stars, rather than dust-enshrouded star formation or AGN activity. The inferred surface mass densities and velocity dispersions for the quiescent galaxies are very high compared to those in local galaxies. The galaxies follow a Kormendy relation (between surface brightness and size) with approximately the same slope as locally, but shifted to brighter surface brightnesses, consistent with a mean stellar formation redshift of z_f~5. This paper demonstrates a direct relation between star formation activity and size at z~2.5, and the existence of a significant population of massive, extremely dense, old stellar systems without readily identifiable counterparts in the local universe.