In this work we study the deformations into Lie bialgebras of the three relativistic Lie algebras: de Sitter, Anti-de Sitter and Poincar\'e, which describe the symmetries of the three maximally symmetric spacetimes. These algebras represent the centrepiece of the kinematics of special relativity (and its analogue in (Anti-)de Sitter spacetime), and provide the simplest framework to build physical models in which inertial observers are equivalent. Such a property can be expected to be preserved by Quantum Gravity, a theory which should build a length/energy scale into the microscopic structure of spacetime. Quantum groups, and their infinitesimal version `Lie bialgebras', allow to encode such a scale into a noncommutativity of the algebra of functions over the group (and over spacetime, when the group acts on a homogeneous space). In 2+1 dimensions we have evidence that the vacuum state of Quantum Gravity is one such `noncommutative spacetime' whose symmetries are described by a Lie bialgebra. It is then of great interest to study the possible Lie bialgebra deformations of the relativistic Lie algebras. In this paper, we develop a classification of such deformations in 2, 3 and 4 spacetime dimensions, based on physical requirements based on dimensional analysis, on various degrees of `manifest isotropy' (which implies that certain symmetries, i.e. Lorentz transformations or rotations, are `more classical'), and on discrete symmetries like P and T. On top of a series of new results in 3 and 4 dimensions, we find a no-go theorem for the Lie bialgebras in 4 dimensions, which singles out the well-known `$\kappa$-deformation' as the only one that depends on the first power of the Planck length, or, alternatively, that possesses `manifest' spatial isotropy., Comment: 13 pages, 1 table, matches version published on Nuclear Physics B