Sou da região do Alto Oeste Potiguar, e fiz estágio aqui mesmo na região e fui efetivo por pouco mais de um ano. Só que só consegui me elevar mais de verdade quando peguei outro trabalho que era home-office em uma empresa maior e mais estruturada. Acho que para quem é de interior (especialmente em cidades pequenas) só tem essas duas opções: se mudar ou pegar um trabalho home-office. Esse foi minha experiência mas acho que essa é a situação geral no país.

Eu acho que se mudar é uma boa (inclusive BH me parece uma cidade bem legal de morar), mas se eu fosse você me mudaria ganhando o suficiente para arcar bem os custos de se manter em grandes centros, que em via de regra são mais caros.

O ideal mesmo para mim seria trabalho home-office morando em um médio/grande centro, assim poderia mudar quando quisesse ou necessário sem se preocupar com o local de trabalho.