We present 9 new tunes of the p-ordered shower and underlying-event model in Pythia 6.4. These "Perugia" tunes update and supersede the older "S0" family. The data sets used to constrain the models include hadronic Z0 decays at LEP, Tevatron min-bias data at 630, 1800, and 1960 GeV, Tevatron Drell-Yan data at 1800 and 1960 GeV, and SPS min-bias data at 200, 546, and 900 GeV. In addition to the central parameter set, called "Perugia 0," we introduce a set of 8 related "Perugia variations" that attempt to systematically explore soft, hard, parton density, and color structure variations in the theoretical parameters. Based on these variations, a best-guess prediction of the charged track multiplicity in inelastic, nondiffractive minimum-bias events at the LHC is made. Note that these tunes can only be used with Pythia 6, not with Pythia 8.