Good maiden post, urbanhiker!
Yes, your points are all well taken.
I would add in the thought that people generally in the first instance accept what they are prepared to believe- but in this case we have a combination of seven Walkers with a relatively narrow perception of time-scale, even Gimli, and two whose perspective is staggeringly wide from a mortal standpoint.
Remember, no Balrog has been seen for nearly
six and a half thousand years.* In real-world terms, that puts us in the Lower Neolithic: man has developed pottery and mud-brick construction, but not writing; history has yet to start. Even the Epic of Gilgamesh isn't that old. Add to that the fact that even the Wise were under the impression that all the Balrogs had been finished off in the War of Wrath, it was an extinct life-form, and the idea of encountering one at the end of the Third Age would be as shocking, as literally incredible, as encountering a real live Neanderthal or saber-toothed cat.
But Legolas and Gandalf don't view time in quite the same way. "Like I said to Moses that time..." Leggy might or might not have been born in the Elder Days, but he still wouldn't be especially freaked out by a millennial time-span; and Olorin, we can assume, actually took part in the Great Battle. This on top of the fact that the two of them might perhaps be more sensitive to the supernatural or 'evil' emanation of the thing (although Gandalf senses a Powerful Being well before he sees and identifies it).
Whereas Aragorn and Boromir, even if well-schooled in the ancient legends (less likely in the case of Boromir), would I think be disposed to think of Balrogs as a matter of ancient history as utterly removed from their real present world as the Silmarils, and thus not disposed to include them on their immediate mental "list of horrible creatures this flame-shadow thing might be". This especially since Middle-earth generally and Moria in particular contain any number of nameless monsters; the two of them had just hacked off the tentacles of one of them not two days before.
Gimli had a ready-made classification and name for the thing, which was of course correct. Just not the whole truth.
---------------
*Except for certain Dwarves, who didn't identify it with the Valaraukar of Angamandi.