We provide strong empirical evidence for a nonlinearity in the Cepheid Period-Luminosity (PL) relations at a number of wavelengths using Galactic, LMC and SMC multi-wavelength data from published sources. We provide a possible theoretical explanation for this that involves the interaction of the stellar photosphere and hydrogen ionization front and show that this has implications for Period-Color and Amplitude-Color (PCAC) relations as well. We extend our analysis to look for nonlinearities in PCAC relations for RR Lyraes. We show the importance of considering the way PL/PC relations vary as a function of period and phase and discuss the implications for stellar modeling, the extra-galactic distance scale and estimate of Hubble constant.