We investigate the structure of neutron stars shortly after they are born, when the entropy per baryon is of order 1 or 2 and neutrinos are trapped on dynamical timescales. In all cases, the thermal effects for an entropy per baryon of order 2 or less are small when considering the maximum neutron star mass. Neutrino trapping, however, significantly changes the maximum mass due to the abundance of electrons. When matter is allowed to contain only nucleons and leptons, trapping decreases the maximum mass by an amount comparable to, but somewhat larger than, the increase due to finite entropy. When matter is allowed to contain strongly interacting negatively charged particles, in the form of strange baryons, a kaon condensate, or quarks, trapping instead results in an increase in the maximum mass of order $0.2M_\odot$, which adds to the effects of finite entropy. The presence of negatively-charged particles has two major implications. First, the value of the maximum mass will decrease during the early evolution of a neutron star as it loses trapped neutrinos, so that if a black hole forms, it either does so immediately after the bounce or it is delayed for a neutrino diffusion timescale of $\sim 10$ s. The latter case is most likely if the maximum mass of the hot star with trapped neutrinos is near $1.5M_\odot$. In the absence of negatively-charged hadrons, black hole formation would be due to accretion and therefore is likely to occur only immediately after bounce. Second, the appearance of hadronic negative charges results in a general softening of the equation of state that may be observable in the neutrino luminosities and average energies. Further, these additional negative charges decrease the electron fraction and may be observed in the relative excess of electron neutrinos compared to other neutrinos.