I'm searching for a proverb or expression that describes a situation which has two choices or two ways out (that is, somewhat of a forced choice) where both lead to some kind of trouble (but not the same trouble).
As an example: Let's say that you can chose to go either left or right. If you go left, you will have to fight your way through an army of trolls. If you go right, you will have to go through a desert without any food or water for one week.
The most common English phrase for this is between a rock and a hard place. It means:
In difficulty, faced with a choice between two unsatisfactory options.
Specifically, to say you are caught between a rock and a hard place means that you are in a dilemma. The exact dilemma seems to be exactly what you're describing--Morton's fork, which is:
a choice between two equally unpleasant alternatives (in other words, a dilemma), or two lines of reasoning that lead to the same unpleasant conclusion. It is analogous to the expressions "between the devil and the deep blue sea," "between a rock and a hard place," or, as those in the Spanish- and Portuguese-speaking world say, "Between a cross and a sword." This is the opposite of the Buridan's Ass.
There are a number of these in English.
Between a rock and a hard place.
Between Scylla and Charybdis.
Between the devil and the deep blue sea.
As well as the closely related expression:
Out of the frying pan and into the fire.
Although you asked for a proverb or expression (which simchona has provided), there's also a single word for this: a dilemma is a choice between equally unappealing options. From the Oxford English Dictionary:
1. In Rhetoric. A form of argument involving an adversary in the choice of two (or, loosely, more) alternatives, either of which is (or appears) equally unfavourable to him. (The alternatives are commonly spoken of as the ‘horns’ of the dilemma.) Hence in Logic, a hypothetical syllogism having a conjunctive or ‘conditional’ major premiss and a disjunctive minor (or, one premiss conjunctive and the other disjunctive).
2. Hence, in popular use: A choice between two (or, loosely, several) alternatives, which are or appear equally unfavourable; a position of doubt or perplexity, a ‘fix’.
One of the example sentences is:
1888 J. Bryce Amer. Commonw. II. liii. 332 They were‥in the dilemma of either violating the Constitution or losing a golden opportunity.
@Phoenix beat me to it:
You're damned if you do and damned if you don't.
Sophie's choice (after the book and movie of the same name) is another option, though it tends to imply that the consequences of either choice are dire, rather than simply unpleasant or undesirable.
The cultural impact of the book gave rise to the expression "making a 'Sophie's Choice'", which describes being forced to choose between two very dear possessions; keeping one and losing the other forever. It is a reference to either of the two central choices Sophie made in the book:
Spoilers follow on the Wikipedia pages.
You may have to choose either "Lesser of two evils" or "Worse of two evils," or just the evils
If you want to use a short phrase that says a little more than just "dilemma", you can go for the Cornelian dilemma.
A few broadly related proverbs (see, e.g., thesaurus.com):
A false dilemma.
A dilemma with two options that are both wrong. There is always a third, more reliable option. Sometimes the choices we have are just current states of a situation, and we lack knowledge to see there is really no choice.
Quoting Wikipedia:
A false dilemma (also called false dichotomy, black-and/or-white thinking, the either-or fallacy, the fallacy of false choice, the fallacy of exhaustive hypotheses, the fallacy of the false alternative or the fallacy of the excluded middle) is a type of informal fallacy that involves a situation in which limited alternatives are considered, when in fact there is at least one additional option. The opposite of this fallacy is argument to moderation.
The options may be a position that is between two extremes (such as when there are shades of grey) or may be completely different alternatives. Phrasing that implies 2 options (dilemma, dichotomy, black and white) may be substituted with other number-based nouns, such as a "false trilemma" if something is reduced to only 3 options, instead of 2.
False dilemma can arise intentionally, when fallacy is used in an attempt to force a choice (such as, in some contexts, the assertion that "if you are not with us, you are against us"). But the fallacy can also arise simply by accidental omission of additional options rather than by deliberate deception.
It's called a Morton's Fork:
A situation involving having to choose between two equally undesirable outcomes.
