We study the early dynamical evolution of young, dense star clusters using Monte Carlo simulations for systems with up to N~10^7 stars. Rapid mass segregation of massive main-sequence stars and the development of the Spitzer instability can drive these systems to core collapse in a small fraction of the initial half-mass relaxation time. If the core collapse time is less than the lifetime of the massive stars, all stars in the collapsing core may then undergo a runaway collision process leading to the formation of a massive black hole. Here we study in detail the first step in this process, up to the occurrence of core collapse. We have performed about 100 simulations for clusters with a wide variety of initial conditions, varying systematically the cluster density profile, stellar IMF, and number of stars. We also considered the effects of initial mass segregation and stellar evolution mass loss. Our results show that, for clusters with a moderate initial central concentration and any realistic IMF, the ratio of core collapse time to initial half-mass relaxation time is typically ~0.1, in agreement with the value previously found by direct N-body simulations for much smaller systems. Models with even higher central concentration initially, or with initial mass segregation (from star formation) have even shorter core-collapse times. Remarkably, we find that, for all realistic initial conditions, the mass of the collapsing core is always close to ~10^-3 of the total cluster mass, very similar to the observed correlation between central black hole mass and total cluster mass in a variety of environments. We discuss the implications of our results for the formation of intermediate-mass black holes in globular clusters and super star clusters, ultraluminous X-ray sources, and seed black holes in proto-galactic nuclei.