We investigate nanocavities at the surface of three-dimensional (3D) photonic crystals, where the polarization-independent surface-mode gap can be utilized. We consider the formation of various nanocavities by introducing artificial defects utilizing the 3D structures around the surface and discuss the possibilities for increasing the Q-factors of the surface nanocavities with TE-like polarization based on the advanced designs of donor-type defects. We also introduce the design of acceptor-type defects and show that TM-like nanocavities are obtained. We then fabricate the designed nanocavities and examine their resonant characteristics; we successfully demonstrate TE-like nanocavities with Q-factors of ~40,000, which is four-times higher than previous surface cavities and as high as that of the cavities embedded inside 3D photonic crystals. TM-like nanocavities with Q-factors of ~22,000 are also demonstrated for the first time.