Self-interacting dark matter (SIDM) models have been proposed to solve the small-scale issues with the collisionless cold dark matter paradigm. We derive equilibrium solutions in these SIDM models for the dark matter halo density profile including the gravitational potential of both baryons and dark matter. Self-interactions drive dark matter to be isothermal and this ties the core sizes and shapes of dark matter halos to the spatial distribution of the stars, a radical departure from previous expectations and from cold dark matter predictions. Compared to predictions of SIDM-only simulations, the core sizes are smaller and the core densities are higher, with the largest effects in baryon-dominated galaxies. As an example, we find a core size around 0.3 kpc for dark matter in the Milky Way, more than an order of magnitude smaller than the core size from SIDM-only simulations, which has important implications for indirect searches of SIDM candidates.