Devo aprender Coreano ou Mandarim primeiro?

Não vejo muitos benefícios em aprender coreano primeiro e depois mandarim ou vice-versa - haverá palavras que soarão semelhantes em ambas as línguas, mas caso contrário não há muitas coisas que tenham em comum. Há mais similaridade entre coreano e japonês, mas no final a ordem em que você aprende uma língua não deve importar muito. Aprender uma língua já é um grande esforço.

A grande vantagem de aprender Mandarim é que é uma língua falada pela maioria das pessoas - portanto será mais útil para você do que o Coreano em muitas circunstâncias. Além disso, você terá mais facilidade em aprender verbos (sem conjugação e sua colocação é semelhante à do inglês) e eu não acho que você tenha que se preocupar com os níveis de fala, em comparação com o coreano. Depois há o fator "legal" - toda vez que seus amigos forem a um restaurante chinês, seu nome será mencionado ;)
O desafio que vejo ao aprender Mandarim é que ele é uma língua tonal, então você tem que ficar confortável em identificar e produzir sons com tons. Além disso, você tem que aprender alguns milhares de caracteres chineses ao invés do alfabeto e isso definitivamente levará algum tempo para se acostumar.

O bom de aprender coreano é que é fácil aprender o alfabeto e você pode começar a ler coisas em coreano muito rapidamente. Também não tem distinções tonais como o inglês, então você não vai ter dor de cabeça por isso. Além disso, muitos coreanos falam um pouco de inglês e são geralmente acolhedores com as pessoas que falam inglês. Então eles tentarão ajudá-lo a aprender coreano mais rápido.
O desafio de aprender coreano é que seu sistema de som é bastante complexo, e você tem que levar algum tempo para compreendê-lo, ao contrário do mandarim que vem com tons, mas de outra forma tem uma pronúncia mais fácil. Você também terá muita dificuldade para passar pelas conjugações verbais que levam em consideração o tempo, a relação entre você e o destinatário, etc. Finalmente, comparado com o mandarim (ou mesmo japonês), você não terá tanta validação social ao falar coreano. Ainda é considerado uma língua menor, embora exista o hallyu e algumas pessoas o reconheçam.

Eu acho que também li que a educação em coreano é um pouco mais complexa do que o japonês, mas eu diria que isso está indo muito técnico e definitivamente fora do escopo para esta questão. Aprender hanja não vai ser muito útil porque os coreanos simplesmente não o usam mais que muitas vezes.
O que quer que seja a sua escolha, vai levar bastante tempo a levar as suas capacidades linguísticas a um nível funcional, por isso pode ser uma boa ideia brincar um pouco com ambas as línguas e depois decidir por si mesmo qual delas você quer comprometer-se a aprender.