Body tides reveal information about planetary interiors and affect their evolution. Most models to compute body tides rely on the assumption of a spherically symmetric interior. However, several processes can lead to lateral variations of interior properties. We present a new spectral method to compute the tidal response of laterally heterogeneous bodies. Compared to previous spectral methods, our approach is not limited to small-amplitude lateral variations; compared to finite element codes, this approach is more computationally efficient. While the tidal response of a spherically symmetric body has the same wavelength as the tidal force; lateral heterogeneities produce an additional tidal response with a spectra that depends on the spatial pattern of such variations. For Mercury, the Moon, and Io, the amplitude of this signal is as high as 1%-10% of the main tidal response for long-wavelength shear modulus variations higher than ∼10% of the mean shear modulus. For Europa, Ganymede, and Enceladus, shell-thickness variations of 50% of the mean shell thickness can cause an additional signal of ∼1% and ∼10% for the Jovian moons and Encelaudus, respectively. Future missions, such as BepiColombo and JUICE, might measure these signals. Lateral variations of viscosity affect the distribution of tidal heating. This can drive the thermal evolution of tidally active bodies and affect the distribution of active regions.