For visible light, a timestep on the order fs is correct. But you have to balance that against the fact that you would typically only need to use FDTD (or any fullwave technique) when your scatterers/structures are on the scale of the wavelength anyway. And since they're so small, the total interaction time is probably not especially long. It's probably in nanoseconds unless they are extremely high Q resonators (and if they are high-Q, use a frequency domain technique directly, like finite elements or method of moments, instead of just waiting ages for a transient solver to reach oscillatory steady state). I don't mean to imply that optical FDTD models are inexpensive, just pointing out that you rarely need to model long time durations with tiny timesteps (and you may have ways to escape, anyway).
When structures are vastly larger than a wavelength (ie too big for full-wave/FDTD) then asymptotic/raytracing-like techniques grow increasingly accurate. They are not bound by the nyquist rate in space nor the courant criteria in time, so their runtime is not so strongly sensitive to frequency (just their accuracy).
I do admit and agree that there's still a large "unconquered middle" of important structures that are electrically/optically large, yet still packed with enough fine detail to demand fullwave accuracy (antenna arrays, photonic crystals, computer chips, many more). Even here, there might be tricks (periodicity, for instance, in the case of an array) that allow for a tailor-made full wave solution.