Por que Gandalf teria medo do Balrog? Bem, é um Balrog. É uma coisa terrível. :)
Mais seriamente, porém, os Balrogs eram seres terríveis, mesmo para Gandalf e outros de seu nível de poder. Os Balrogs também são Maia, assim como Gandalf e o resto dos Istari. Veja aqui do Valaquenta, o segundo livro do Silmarillion:
Não apenas os Balrogs estão na mesma escala de Gandalf, eles eram seres de terror e fogo para começar, enquanto Gandalf, apesar de todo o seu poder, não era um guerreiro. Ele é descrito como "o mais sábio dos Maiar", e como servo de Manwë, e de Nienna, e de Lórien, o Valar da sabedoria e julgamento e misericórdia e sonhos, e não de Tulkas ou Oromë, os Valar mais guerreiros. / p>For of the Maiar many were drawn to his splendour in the days of his greatness, and remained in that allegiance down into his darkness; and others he corrupted afterwards to his service with lies and treacherous gifts. Dreadful among these spirits were the Valaraukar, the scourges of fire that in Middle-earth were called the Balrogs, demons of terror.
Adicionalmente, você tem que lembrar que na cosmologia de Tolkien, o mais velho é sempre melhor. O mundo está sempre em estado de decadência. As maravilhas dos Valar quando o mundo era novo nunca poderiam ser superadas até mesmo pelas maiores obras dos elfos da Primeira Era. Mesmo Silmarils de Feanor eram apenas um eco da luz das árvores. Da mesma forma, as mãos do Homem da Terceira Idade nunca poderiam produzir obras tão boas quanto as Smiths of Eregion na Segunda Era, e certamente não das obras do próprio Feanor.
Portanto, tendo isso em mente, lembramos que os Balrogs foram os Capitães de Morgoth durante as guerras da Primeira Era. Tomou todo o poder de Ecthelion, Senhor da Fonte e um dos maiores capitães de Gondolin e elvendom para derrotar Gothmog, senhor dos Balrogs, e ele levou-o consigo para a sua morte.
Então, quando Gandalf ouviu que um Balrog ainda se esconde nas profundezas de Moria, é claro que ele teria medo. Um Balrog é um terror da Primeira Era. E algo que era uma ameaça na Primeira Era seria um terror incontrolável no Terceiro.