The spinless Falicov-Kimball model is solved exactly in the limit of infinite dimensions on both the hypercubic and Bethe lattices. The competition between segregation, which is present for large U, and charge density-wave order, which is prevalent at moderate U, is examined in detail. We find a rich phase diagram that displays both of these phases. The model also shows nonanalytic behavior in the charge-density-wave transition temperature when U is large enough to generate a correlation-induced gap in the single-particle density of states.