  The evolution of the universe prior to Big Bang Nucleosynthesis could have
gone through a phase of early matter domination (EMD) which enhanced the growth
of small-scale dark matter structure. If EMD was long enough, self-gravitating
objects formed prior to reheating. We study the evolution of these dense early
halos (EHs) through reheating. At the end of EMD, EHs undergo rapid expansion
and eventually eject their matter. We find that this process washes out
structure on scales much larger than naively expected from the size of the
original halos. We compute the density profiles of the EH remnants and use them
to construct late-time power spectra that include these non-linear effects. EH
dynamics limits the maximum enhancement that can be generated by EMD in a way
that is independent of the dark matter microphysics. We evolve an extrapolated
$\Lambda$CDM power spectrum to estimate the properties of microhalos that would
form after matter-radiation equality. Surprisingly, cosmologies with a short
period of EMD lead to an earlier onset of microhalo formation compared to those
with a long period of EMD. In either case, dark matter structure formation
begins much earlier than in the standard cosmology, with most DM bound in
microhalos.
