We investigate the origin of the relations between stellar mass and optical circular velocity for early-type (ETG) and late-type (LTG) galaxies --- the Faber-Jackson (FJ) and Tully-Fisher (TF) relations. We combine measurements of dark halo masses (from satellite kinematics and weak lensing), and the distribution of baryons in galaxies (from a new compilation of galaxy scaling relations), with constraints on dark halo structure from cosmological simulations. The principle unknowns are the halo response to galaxy formation and the stellar initial mass function (IMF). The slopes of the TF and FJ relations are naturally reproduced for a wide range of halo response and IMFs. However, models with a universal IMF and universal halo response cannot simultaneously reproduce the zero points of both the TF and FJ relations. For a model with a universal Chabrier IMF, LTGs require halo expansion, while ETGs require halo contraction. A Salpeter IMF is permitted for high mass (sigma > 180 km/s) ETGs, but is inconsistent for intermediate masses, unless V_circ(R_e)/sigma_e > 1.6. If the IMF is universal and close to Chabrier, we speculate that the presence of a major merger may be responsible for the contraction in ETGs while clumpy accreting streams and/or feedback leads to expansion in LTGs. Alternatively, a recently proposed variation in the IMF disfavors halo contraction in both types of galaxies. Finally we show that our models naturally reproduce flat and featureless circular velocity profiles within the optical regions of galaxies without fine-tuning.