We present a general theory of three-dimensional nonparaxial spatially-accelerating waves of the Maxwell equations. These waves constitute a two-dimensional structure exhibiting shape-invariant propagation along semicircular trajectories. We provide classification and characterization of possible shapes of such beams, expressed through the angular spectra of parabolic, oblate and prolate spheroidal fields. Our results facilitate the design of accelerating beams with novel structures, broadening scope and potential applications of accelerating beams.