|MadSci Network: Astronomy|
You seem to have nearly answered your own question, as it turns out. Here's a long-winded explanation of how we measure altitudes on the surfaces of planets:
The simplest way to measure the altitude of, say, the top of a mountain would be to give how far it is from the center of the planet. This is easy and right to the point, in one sense. But it is also very silly. Comparing the height of Olympus Mons to Everest would be impossible, since Earth and Mars are different sizes to begin with. So we could do the obvious thing and set an arbitrary distance from the center of the planet as 0 altitude and measure heights above (and below, as needed) this reference. Planets are pretty smooth, if you look at them globally, as well as pretty spherical, so you could easily define some reference radius as I described. But this is not the whole story.
First of all, planets are not quite spherical. Their rotation flattens them at the poles and bulges them at the equator. For the Earth, the difference is around 10 kilometers between the circumference of the equator and the circumference of a circle passing through both poles. Since the Earth is 6378 km in radius, this is not really that much. Still, mountains are generally a few kilometers tall, so this correction is worth making! So you can imagine taking your sphere and making into an ellipsoid (a flattened sphere).
This is actually pretty accurate, but on Earth, we use a different system. "Sea-level" is an obvious reference point on our watery planet, especially since oceans are pretty smooth compared to land features. But the oceans do not quite shape themselves to fit this ellipsoid! The reason is a bit subtle: water flows until it has made its surface perpendicular to the force at that point. If it were not arranged in this way, it would be forced to flow sidewise and reshape itself under the local force. What is this force? The biggest one is gravity, while the "centrifugal" force of the Earth spin also contributes. (My physics teachers of yore would like me to point out that there is no such force as "centrifugal" force, in reality. It is just the result of inertia, as seen on a spinning body. However, I think it easier to talk about centrifugal force than to always be thinking about how things look in a non-spinning view-point.) "But wait!" you are undoubtedly saying, "Didn't we just take care of all of this with our ellipsoid in the last paragraph?" Almost, but not quite. We usually treat planets as if all of their mass were located in a single point at their centers. This works well, usually, but it isn't quite true. There are small deviations from this that can lead to a slightly different force of gravity than what you would have expected. We humans do not notice this, but water does. So we introduce the concept of the geoid, the surface that water would take if the whole planet were covered in water. The difference between the ellipse above and the geoid is at most -106 to +85 meters on the Earth.
So now we have not one but three ways to measure the altitudes of objects on planets. In all three, we need to define a reference altitude somehow and then use the appropriately shaped surface as a reference. Usually, we just set things up so that the average reference surface is as close as possible to the planet's real surface, just like our "sea-level" on Earth.
There is a subtle point here, however, when it comes to measuring the heights of mountains. Namely, height and altitude are different things. Altitude is how far above the reference level your mountain gets. Height is the difference between the altitude of the top of the mountain and the base of the mountain. Who cares? Well, Alaskans do, for example. The highest (greatest altitude) mountain on the Earth is Mt. Everest. But Everest is in the Himalayan mountain range, so its base is already at a high altitude. Mt McKinley in Alaska is the tallest (greatest height) mountain on Earth, or at least on land. Hawaii's islands are actually even taller, rising up off the floor of the Pacific. But they start lower than Everest, and therefore never get the same altitude.
What about Mars? Olympus Mons is an isolated volcanic mountain, so its base is also pretty nearly on the geoid. The 24 km altitude is also the height, so Olympus Mons is, in fact, taller than Everest.
Here a nice page with some information on Earth's geoid.
Try the links in the MadSci Library for more information on Astronomy.