(ABRIDGED) We present a semi-analytic model to explore merger histories, destruction rates, and survival probabilities of substructure in dark matter halos and use it to study the substructure populations of galaxy-sized halos as a function of the power spectrum. We successfully reproduce the subhalo velocity function and radial distribution seen in N-body simulations for standard LCDM. We explore the implications of spectra with normalizations and tilts spanning sigma_8 = 0.65-1 and n = 0.8-1. We also study a running index (RI) model with dn/dlnk=-0.03, as discussed in the first year WMAP report, and several WDM models with masses m_W = 0.75, 1.5, 3.0 keV. The substructure mass fraction is relatively insensitive to the tilt and overall normalization of the power spectrum. All CDM-type models yield projected substructure mass fractions that are consistent with, but on the low side of, estimates from strong lens systems: f = 0.4-1.5% (64 percentile) in systems M_sub < 10^9 Msun. Truncated models produce significantly smaller fractions and are disfavored by lensing results. We compare our predicted subhalo velocity functions to the dwarf satellite population of the Milky Way. Assuming isotropic velocity dispersions, we find the standard n=1 model overpredicts the number of MW satellites as expected. Models with less small-scale power are more successful because there are fewer subhalos of a given circular velocity and the mapping between observed velocity dispersion and halo circular velocity is markedly altered. The RI model, or a fixed tilt with sigma_8=0.75, can account for the MW dwarfs without the need for differential feedback; however, these comparisons depend sensitively on the assumption of isotropic velocities in satellite galaxies.