In a proof by contradiction, what if both the proposition and its negation lead to contradictions?

If both $C$ and $\neg C$ lead to a contradiction, then you must be working with an inconsistent set of assumptions ... from which anything can be inferred ... including $\neg C$. As such, $\neg C$ can still be concluded given that assumption $C$ leads to a contradiction.

So, regardless of whether $\neg C$ also leads to a contradiction or whether it does not, we can conclude $\neg C$ once assumption $C$ leads to a contradiction.

The thing to remember is that when in logic we say that we can 'conclude' something, we mean that that something follows from the assumptions ... not that that something is in fact true. I think that's the source of your confusion. You seem to be saying: "OK, if $C$ leads to a contradiction, then we want to say that $\neg C$ is true ... But wait! What if $\neg C$ leads to a contradiction as well .. wouldn't that mean that $\neg C$ cannot be true either? So, how can we say $\neg C$ is true?!". But it's not that $\neg C$ is true .. it's just that it logically follows from the assumptions. That is: if the assumptions are all true, then $\neg C$ will be true as well. Well, are they? .. and is it? Funny thing is, as logicians, we don't really care :)

why is it that $C$ leading to a contradiction must mean that $\neg C$ is true?

Rather: why does $\def\false{\mathsf{contradiction}} A,\neg B, C\vdash \false$ let us infer that $A,\neg B\vdash \neg C$

Well, $A,\neg B,C\vdash \false$ means that $\false$ is true assuming that $\{A,\neg B, C\}$ all are true.   However, a $\false$ is, by definition, false, so that informs us that at least one from $\{A,\neg B, C\}$ must be false.   Thus when we assume that $\{A,\neg B\}$ are both true, we are implicating that $C$ is false.   That is $A,\neg B\vdash \neg C$

Notice: We are not unconditionally declaring that $\neg C$ is true; we are asserting that it is so under assumption that $A$ and $\neg B$ are true.

What if $\neg C$ also leads to a contradiction?

Why, if we can prove $A,\neg B,C\vdash \false$ and also that $A,\neg B,\neg C\vdash \false$ then we have shown that: at least one from $\{A,\neg B, C\}$ and at least one from $\{A,\neg B,\neg C\}$ are false; simultaneously even.   Since we usually accept that $C$ cannot have two different truth assignments at once (the law of noncontradiction: $\neg(\neg C\wedge C)$) we must conclude that at least one from $\{A,\neg B\}$ are false.   Therefore we infer from those two proofs that that: $A,\neg B\vdash\false$.$$\begin{split}A,\neg B,C &\vdash \false\\ A,\neg B,\neg C&\vdash\false\\\hline A,\neg B&\vdash \false\end{split}\text{ because } \begin{split}A,\neg B &\vdash \neg C\\ A,\neg B&\vdash\neg\neg C\\\hline A,\neg B&\vdash \false\end{split}$$

Good question! There are some mathematicians who do not agree that the Law of the Excluded Middle is valid, and therefore accept only direct proofs as sound, not proofs by contradiction. They would say your intuition is on to something important. If you’re using rules of logic that don’t explode when they encounter $p∧¬p$, that is, a logic that does not state that an inconsistency proves that all statements are vacuously true, you’re using a paraconsistent logic. If you can prove a contradiction, and still think the theory is of interest, you’re doing inconsistent mathematics.

In mainstream mathematics and philosophy, however, such a result would prove that the formal system you were using is inconsistent. In a traditional logic, such as the axioms of logic defined by David Hilbert, it means that all (well-formed) statements become vacuously true as theorems within that system. The proof system generated by the single premise “False” and containing all other statements as theorems with the same one-line proof is too trivial to be interesting, and you’d have shown the inconsistent system to be equivalent to the trivial one under traditional logic, so an inconsistent theory would be abandoned. But, since there had been some reason people were using the theory before, they would then ask, “Can we rescue the parts of this theory we care about? Change the axioms to make them consistent, and still have a interesting theory, maybe even a useful one?”

The best-known example is probably when Frege attempted to prove that all of mathematics could be founded in set theory. In his theory, it was permissible to define the set of all sets with some property. Bertrand Russell proved that this led to Russell’s Paradox: does the set of all sets that do not contain themselves, contain itself? Thus, the theory was proven inconsistent.

Frege withdrew his book, but people kept working on the problem. The long-term result was the development of Zermelo-Frankel set theory, which most mathematicians use as the underlying basis for their work today. It has different axioms that allow you to prove the existence of sets corresponding to the natural numbers, the real numbers, matrices, sequences, and all the other structures we need to do mathematics as we presently understand it. However, (and this is not a rigorous explanation) they are intentionally limited so that you cannot prove the existence of a set that contains itself, or anything like one.

Also keep in mind that, by Gödel’s Second Incompleteness Theorem, it is impossible for a formal system both complex enough to contain arithmetic, and also consistent, to prove its own consistency. At least not in a finite number of steps.