Using deep NIR VLT ISAAC and optical HST WFPC2 imaging in the HDF-S and MS 1054-03, we study the rest-frame UV-to-optical colors and magnitudes of galaxies to z~3. Unlike the present day, there is no evidence for a red sequence at z~3, but there does appear to be a well-defined CMR for blue galaxies at all redshifts, with more luminous galaxies having redder U-V colors. The slope of the blue CMR is independent of redshift δ(U-V)/δMV=-0.09+/-0.01 and can be explained by a correlation of dust reddening with luminosity. The average color at fixed luminosity reddens strongly Δ(U-V)~0.75 from z~3 to z=0, much of which can be attributed to aging of stars. The color scatter of the blue sequence is relatively small σ(U-V)=0.25+/-0.03 and constant to z~3, but notably asymmetrical, having a sharp blue ridge and a wing toward redder colors. We explore sets of SFHs to study the constraints placed by the shape of the scatter at z=2-3. One particular set of models, episodic star formation, reproduces the detailed properties very well. For a two-state model with high and low star formation, the duty cycle is constrained to be >40% and the contrast in SFR between the states must be a factor >5 [or a scatter in log(SFR) of >0.35 dex around the mean]. Nevertheless, episodic models do not explain the observed tail of very red galaxies, primarily DRGs, which may have ceased star formation altogether or are more heavily obscured. Finally, the relative number density of red, luminous MV<-20.5 galaxies increases by a factor of ~6 from z=2.7 to 0.5, as does their contribution to the total rest-frame V-band luminosity density. We are likely viewing the progressive formation of red, passively evolving galaxies. Based on service mode observations collected at the European Southern Observatory, Paranal, Chile (ESO Program 164.O-0612). Based on observations with the NASA/ESA Hubble Space Telescope, obtained at the Space Telescope Science Institute, which is operated by AURA, Inc., under NASA contract NAS5-26555.