If there were an easy solution to this, Camera manufacturers would have built it in-camera (and cashed out) long ago :)
Here's the problem.
The best modern cameras are sensitive to at most ~15 stops of dynamic range, whereas estimates have put the dynamic range of the human eye at around 20 stops (see this post, for example). In short, your camera can't see as well as you; and when you encounter high-contrast scenes like this, it's up to you to determine how to realize your creative vision while compensating for those limits.
Some approaches you may be interested in:
- Dodging and burning, i.e., selectively lightening or darkening areas of your exposure. In concept, it's been used since the dawn of photography.
- Exposure bracketing, which can be used in post-processing to blend two or more exposures together (usually: one or more underexposed, one correctly exposed, and one or more overexposed)
- Related to the above: many modern software tools will orchestrate this for you, usually referred to as "HDR".
- EDIT: See also @David Rouse's excellent response for more ways to approach this in Photoshop. Curves, in particular, can be a wonderful step up from levels (the latter has three variable parameters, while you could go crazy with curves).
Of course, there are many more approaches — experiment, and see what works for you!
To put it another way — when you up the contrast, your editor is doing exactly what you tell it to: making the shadows darker, and highlights lighter.
If the difference between your shadows and highlights is too great... you can always flatten out your tone curve, which is what HDR does. Here's the histogram from a RAW file I shot at sunset in Brooklyn showing significant clipping in both the shadows and the highlights:

And here's the histogram after exposure blending my bracketed shots:

Still needs work; but you've got all the dynamic range there to work with. Note that this can make your shot look super unnatural
if you're not judicious with it.
Hope this helps!