We investigate the nature of the substantial population of high-redshift galaxies with Js-Ks>=2.3 colors recently discovered as part of our Faint Infrared Extragalactic Survey (FIRES). This color cut efficiently isolates galaxies at z>2 with red rest-frame optical colors (``distant red galaxies'' [DRGs]). We select Js-Ks>=2.3 objects in both FIRES fields, the ~2.5m×2.5m Hubble Deep Field-South (HDF-S) and the ~5'×5' field around the MS 1054-03 cluster at z=0.83; the surface densities at Ks,Vega<21 mag are 1.6+/-0.6 and 1.0+/-0.2 arcmin-2, respectively. We here discuss a subsample of 34 DRGs at 2<=z<=3.5: 11 at Ks,Vega<22.5 mag in HDF-S and 23 at Ks,Vega<21.7 mag in the MS 1054-03 field. This sample enables for the first time a robust assessment of the population properties of DRGs. We analyze the λ=0.3-2.2 μm spectral energy distributions (SEDs) constructed from our very deep near-infrared (NIR) and optical imaging collected at the ESO Very Large Telescope and from the Hubble Space Telescope. We develop diagnostics involving the I814-Js, Js-H, and H-Ks colors to argue that the red NIR colors of our DRG sample cannot be attributed solely to interstellar dust extinction and require for many the presence of an evolved stellar population with a prominent Balmer/4000 Å break. In the rest frame, the optical colors of DRGs fall within the envelope of normal nearby galaxies and the ultraviolet colors suggest a wide range in star formation activity and/or extinction. This is in stark contrast with the much bluer and more uniform SEDs of Lyman break galaxies (LBGs). From evolutionary synthesis modeling assuming constant star formation (CSF), we derive for the DRGs old ages, large extinctions, and high stellar masses, mass-to-light ratios, and star formation rates (SFRs). For solar metallicity, a Salpeter initial mass function (IMF) between 0.1 and 100 Msolar, and the Calzetti et al. extinction law, the median values for the HDF-S (MS 1054-03 field) sample are 1.7 (2.0) Gyr, AV=2.7 (2.4) mag, M*=0.8(1.6)×1011 Msolar, M*/LV,*=1.2 (2.3) Msolar L-1V,solar, and SFR=120 (170) Msolar yr-1. Models assuming exponentially declining SFRs with e-folding timescales in the range from 10 Myr to 1 Gyr generally imply younger ages, lower extinction, and lower SFRs, but similar stellar masses within a factor of 2. Compared to LBGs at similar redshifts and rest-frame V-band luminosities, DRGs are older, more massive, and more obscured for any given star formation history. For the entire sample of Ks-band selected galaxies in the FIRES fields at 2<=z<=3.5 and to the above magnitude limits, we find that the derived ages, extinctions, and stellar masses increase with redder Js-Ks colors. Although the rest-frame optical colors of the DRGs are similar to those of local normal galaxies, the derived properties are quite different; detailed studies of this new z>2 population may significantly enhance our understanding of how massive galaxies assembled their stellar mass. Based on observations collected at the European Southern Observatory, Paranal, Chile (ESO LP Programme 164.O-0612). Based on observations with the NASA/ESA Hubble Space Telescope obtained at the Space Telescope Science Institute, which is operated by AURA, Inc., under NASA contract NAS5-26555. Based on observations obtained at the W. M. Keck Observatory, which is operated jointly by the California Institute of Technology and the University of California.