Non-linear special relativity (or doubly special relativity) is a simple framework for encoding properties of flat quantum space-time. In this paper we show how this formalism may be generalized to incorporate curvature (leading to what might be called ``doubly general relativity''). We first propose a dual to non-linear realizations of relativity in momentum space, and show that for such a dual the space-time invariant is an energy-dependent metric. This leads to an energy-dependent connection and curvature, and a simple modification to Einstein's equations. We then examine solutions to these equations. We find the counterpart to the cosmological metric, and show how cosmologies based upon our theory of gravity may solve the ``horizon problem''. We discuss the Schwarzchild solution, examining the conditions for which the horizon is energy dependent. We finally find the weak field limit.