The classical notion of rigidity (that a formation of agents in R-2 or R-3 is rigidly constrained by interagent distances up to rigid-body transformations of space) is inherently dependent on the nature of Euclidean space and the nature of distance measurements. In this paper, we present a generalized formulation of rigidity, where agent states may lie in heterogeneous and non-Euclidean state spaces with arbitrary differentiable measurement constraints. A key aspect of our approach is to recognize the crucial role that the symmetry action of rigid-body transformations plays in classical rigidity theory. We consider a general symmetry given by a Lie-group action on a heterogeneous state space and define global rigidity of a formation to be the case where the interagent measurements fully constrain the agent locations up to the invariance encoded by the group action. In this framework, we develop general definitions of local rigidity and infinitesimal rigidity and introduce a new notion of robust rigidity that we believe will be important for control applications. To motivate the development, we show how the proposed theory can be applied to generalizations of the established problems of network localization and formation control. The provided results are directly applicable to networks of robotic vehicles involving a mixture of bearing and distance sensors, as well as cases where a collection of ground, submersible, and aerial vehicles operate in a single formation.