In this chapter, we review the theory of surface electromagnetic waves in gradient media with arbitrary surface gradients of dielectric permittivity and magnetic permeability. We particularly focus on novel low-loss propagating surface wave solutions found in gradient media where both dielectric permittivity and magnetic permeability are dominated by their imaginary parts. Several examples of gradient geometries where the surface wave problem can be solved analytically are discussed. We present practical examples of surface wave geometries, ranging from radio communication underwater to UV nanophotonics. Specifically, we demonstrate that a gradual interface between gold and silver supports the propagation of a novel type of surface electromagnetic wave, distinct from the more well-known surface plasmon polaritons. The existence of such surface waves creates a paradoxical situation where a continuous metal barrier without any pinholes can exhibit significantly increased light transmission if the barrier is made of two different metals.