How do Catholics and Eastern Orthodox justify their clergy praying with those big hats on their heads?

The 1917 Code of Canon Law says:

Canon 1262 §2. Men, in a church or outside a church, while they are assisting at sacred rites, shall be bare-headed, unless the approved mores of the people or peculiar circumstances of things determine otherwise; women, however, shall have a covered head and be modestly dressed, especially when they approach the table of the Lord.

Head coverings of the clergy (e.g., skullcaps, birettas, etc.) indicate ecclesiastical dignity; thus, they are permitted even inside churches. Generally priests only wear birettas when they want to indicate authority (e.g., the authority to preach a homily), and they will take it off after approaching the altar. (See this video.)

Other exceptions would be, for example, a police or military officer or someone else of such authority attending a funeral Mass. He could wear his formal uniform, including hat, even in church.

I don't know if you've ever read Baruch, but it's the only instance of the word mitre I could find in the Bible

Jerusalem, take off your robe of mourning and misery; put on the splendor of glory from God forever: wrapped in the cloak of justice from God, bear on your head the mitre that displays the glory of the eternal name. For God will show all the earth your splendor: you will be named by God forever the peace of justice, the glory of God's worship.

Bar 5:1-4 - Roman Missal 2nd Sunday of Advent

And even here I think they've changed the translation from mitre to diadem in the NABRE. But, it would have been a good and useful instance of worshiping God while clad in a fancy hat.

Nevertheless, you're obviously talking about a New Testament injunction. And I won't offend you by asking why you permit your women to pray uncovered nor will I call you a hypocrite by asking how you manage to "pray without ceasing" as St. Paul also says you should do, because this is a good question which is hard to answer because as far as I could tell the instruction for bishops (like Pope Francis) to remove their mitres or zucchetos is not in the GIRM (General Instruction of the Roman Missal). But upon further digging (Somewhere between EWTN to Zenit) I found something awesome I never heard of before called the Ceremonial of Bishops and that's got all the particulars. I don't have the book and I couldn't get exactly why you want to know (proof for Andrew Leachs well founded assertion in the comments) in link form, but I did find it quoted elsewhere:

"the bishop does not use the miter: during the introductory rites, the opening prayer, prayer over the gifts, and prayer after communion; during the general intercessions, the Eucharistic prayer, the gospel reading, hymns that are sung standing …."

Fr. Edward McNamara LC quoting the Ceremonial of Bishops - Zenit 3-15-2013

Now, the Mass in and of itself is a prayer, the greatest of prayers, but the parts that the Bishop is involved in where it is obvious that he is praying, he does not wear his mitre.

But the more important point, because a Biblical injunction is so specific here:

The bishop wears his zucchetto, or skullcap, throughout the Mass except from the beginning of the Eucharistic Prayer until he has returned to the cathedra on concluding the administration of holy Communion.

and you'll see that if you ever watch Mass on a Solemnity on EWTN or in person at your local cathedral. Bishops always have someone ready to nab their hats, it's all very well documented and exceptionally rigorously laid out that at the very important times, Bishops will remove their hats.

But I think it is out of respect for the solemnity of what is happening, not the act of praying, but the fact of being in the presence of the Lord.

Orthodox bishops, priests and monks always remove their hats (of whatever kind) when praying. The Bishop removes his mitre at the Altar. Monks hang their klobuk over their shoulder or remove it entirely during the service. So the question seems to stem from ignorance, or not actually attending an Orthodox Liturgy to see what we do. Incidentally it is correct for monks (and Orthodox bishops are monks) to keep their klobuks on during much of the Offices.