Your distinction between "description" and "explanation" is interesting. It seems like "explanation" is very much what you describe in your second sentence: describing how an observation is a consequence of a broader array of forces from which other, diverse phenomena also emerge.

So you can explain a theory in much the same way by embedding it in a yet broader basis that explains multiple theories. For example, the theory of magnetism was long ago explained as a special case of electromagnetism, and now of the electroweak force. In the same way, gravity could be explained by quantum field theory or string theory, but more work needs to be done to do so.

Your feeling of disappointment might come from the issue of "intuition," which can make explanations feel satisfying. Many explanations for everyday things feel intuitive; they "make sense" because they fit patterns that we're familiar with. Many physics theories are deeply unintuitive unless you spend time with the detailed math. That doesn't mean the explanations aren't explanations; it just means that they don't feel satisfying (without intense studying).

Eistein's original formulation of SR required two postulates: that the laws of physics are indistinguishable between any two inertial reference frames, and that the speed of light is constant in all inertial reference frames. Both of these are experimentally motivated.

However, that's not the only way to obtain SR. You can, for example, assume Maxwell's equations (or any of the higher-level electrodynamic field formulations) and postulate #1, and obtain the invariant speed of light as the only valid solution for self-propagating EM waves in free space. I rather prefer this formulation, as the EM field formulation feels more "fundamental" than a fixed speed of light.

You can also derive SR from postulate #1 and some properties of space: isotropy, homogeneity, and memorylessness.

This is a pretty good explanation: http://news.ycombinator.com/item?id=1631206

You've got two problems, though: 1) We don't yet have a consistent explanation for what gravity is. General Relativity is good, but breaks down at small distances. 2) At some point, physics becomes math, and at some point after that there are no explanations. For example, why does 1=1? Basically, the answer is "by definition".