It is unclear whether anyone even knew Gandalf was a Maia
...save Elrond, Círdan, and Galadriel themselves.
Word of God
Tolkien says this in the Unfinished Tales:
Wizard is a translation of Quenya Istar: one of the members of an "order" (as they call it), claiming to possess, and exhibiting, eminent knowledge of the history and nature the World. The translation (through suitable in its relation to "wise" and other ancient words of knowing, similar to that of istar in Quenya) is not perhaps happy, since Heren Istarion or "Order of Wizards" was quite distinct from "wizards" and "magicians" of later legend; they belonged solely to the Third Age and then departed, and none save maybe Elrond, Círdan and Galadriel discovered of what kind they were or whence they came.
Unfinished Tales, Part II, The Istari
Which would make sense. The Istari came in secret to Middle-earth, and no one (save the aforementioned trio) found out about that. And you may wonder how these three found out, when the Istari didn't tell anyone about their past.
The easiest to explain. He's the guy who's in charge of the Grey Havens, and is one of the wisest (and oldest) of the Elves remaining in Middle-earth. It's clear Círdan saw what Gandalf was, as he gives him Narya, one of the 3 Elven Rings – themselves being 3 out of the 20 Rings of Power – when Gandalf first arrives in Middle-earth (which is in itself a tell-tale sign of where he came from).
"Take this ring, Master, for your labours will be heavy; but it will support you in the weariness that you have taken upon yourself. For this is the Ring of Fire, and with it you may rekindle hearts in a world that grows chill. But as for me, my heart is with the Sea, and I will dwell by the grey shores until the last ship sails. I will await you."
The Lord of the Rings: The Return of the King, Appendix B
Another one of the wisest Elves in Middle-earth, he's also the son of Eärendil, the only Half-Elven at that time ever to be admitted into Valinor. He's also been around for 3 Ages, albeit only for a little while having been born near the end of the First Age. He's also the bearer of Vilya, one of the 3 Elven Rings.
Similar to Elrond, and Cirdan, Galadriel has lived in Middle-earth for 3 Ages, and she's far older than Elrond. The bearer of Nenya, and also knew what a Maia was - she was friends with Melian, the wife of Thingol who was a Maia.
So how did Elrond and Galadriel find out?
Elrond and Galadriel did not find out Gandalf's race by themselves. They were actually told by Círdan, who as explained above found out only because he was at the Havens when Gandalf arrived. I do feel that they would eventually have pieced things together and realised what Gandalf was. Galadriel herself had probably met a few Maiar during her time in Valinor. After a few centuries of not aging even Elves would begin to wonder what the Istari were, and probably only those who have been around long enough would be able to connect the dots.
Even as the first shadows were felt in Mirkwood there appeared in the west of Middle-earth the Istari, whom Men called the Wizards. None knew at that time whence they were, save Círdan of the Havens, and only to Elrond and to Galadriel did he reveal that they came over the Sea.
The Silmarillion, Of the Rings of Power and the Third Age
Other beings in Middle-earth
That being said, what about other beings in Middle-earth? Surely they too would have thought it strange to see this bearded old men outliving themselves (Men), or simply hanging around for so long (Elves).
We aren't told for certain what Elves knew of the Istari. Surely the Elven-wise may have at least guessed what the Istari were, but other Elves would probably not know for certain. Most of the Elves in Middle-earth were of the Sindar; those who had never been to Valinor, either because their ancestors stayed behind with King Thingol or because they were born in the Second or Third Ages. But the Elven-wise, at least may have had some idea.
In Rivendell there live still some of his chief foes: the Elven-wise, lords of the Eldar from beyond the furthest seas. They do not fear the Ringwraiths, for those who have dwelt in the Blessed Realm live at once in both worlds, and against both the Seen and the Unseen they have great power.
The Lord of the Rings: The Fellowship of the Ring, Book II, Chapter I: Many Meetings
It's likely Glorfindel knew. He returned to Middle-earth after his death in the First Age, and was wise enough to discern what the Istari were, as he himself was an emissary of the Valar. It's never stated however.
It's said that Men mistook Gandalf and the other Istari to be of the Elven-kind. Which is itself incorrect, of course, but further reinforces my stand that no one really knew what the Istari were. Certainly not Barliman Butterbur, and not even Denethor.
Mostly he journeyed unwearingly on foot, leaning on a staff; and so he was called among Men of the North Gandalf, “the Elf of the Wand”. For they deemed him (though in error, as has been said) to be of Elven-kind, since he would at times works wonders among them, loving especially the beauty of fire; and yet such marvels he wrought mostly for mirth and delight, and desired not that any should hold him in awe or take his counsels out of fear.
Unfinished Tales, Part II, The Istari
It may be worthy to note that Gandalf also tells Faramir the name he took in Valinor: Olórin.
'Mithrandir we called him in elf-fashion,' said Faramir, 'and he was content. Many are my names in many countries, he said. Mithrandir among the Elves, Tharkûn to the Dwarves; Olórin I was in my youth in the West that is forgotten, in the South Incánus, in the North Gandalf; to the East I go not.'
The Lord of the Rings: The Two Towers, Book IV, Chapter V: The Window on the West
Sure, Faramir was learned in the lore of Gondor and the history of his people. He's aware of the Blessed Land and those residing there. But he has never seen a Maia before, not unlike Galadriel, Elrond or even Glorfindel. He couldn't have known Gandalf was a Maia; all he knew is that he came from Valinor as a messenger.
Treebeard isn't too sure either, and himself a very old being. At best we have this quote, where he merely states what he knows about a Wizard: that Gandalf and Saruman are of that order, and that they came from Valinor. We can guess that the other Ents knew as much as Treebeard, if they cared to know.
‘Saruman is a Wizard,’ answered Treebeard. ‘More than that I cannot say. I do not know the history of Wizards. They appeared first after the Great Ships came over the Sea; but if they came with the Ships I never can tell.
The Lord of the Rings: The Two Towers, Book III, Chapter IV: Treebeard
From The History of Middle-earth, Tolkien suggests that Sauron wasn't entirely sure what the Istari were, just that the Valar sent them as emissaries.
If he thought about the Istari, especially Saruman and Gandalf, he imagined them as emissaries from the Valar, seeking to establish their lost power again and 'colonize' Middle-earth, as a mere effort of defeated imperialists (without knowledge or sanction of Eru). His cynicism, which (sincerely) regarded the motives of Manwë as precisely the same as his own, seemed fully justified in Saruman. Gandalf he did not understand.
The History of Middle-earth: Morgoth's Ring (Book 10)
I'm sure he may have been able to piece things out: surely they weren't Men or Elves – and he himself was a Maia – but we're not told.
In general, Hobbits knew nothing more of Istari than Men did. They were perceived as just a "Wizard" so to speak.
That was Gandalf's mark, of course, and the old man was Gandalf the Wizard, whose fame in the Shire was due mainly to his skill with fires, smokes, and lights. His real business was far more difficult and dangerous, but the Shire-folk knew nothing about it. To them he was just one of the 'attractions' at the Party. Hence the excitement of the hobbit-children. 'G for Grand!' they shouted, and the old man smiled. They knew him by sight, though he only appeared in Hobbiton occasionally and never stopped long; but neither they nor any but the oldest of their elders had seen one of his firework displays they now belonged to the legendary past.
The Lord of the Rings: The Fellowship of the Ring, Book I, Chapter I: A Long-expected Party
What people perceived the Istari were mainly depended on how much they already knew about the beings in Valinor. Most Men aren't aware, barring some Men who were learned in lore (Aragorn, Faramir and Denethor perhaps), and merely mistook the Istari as Elves. Elves on the other hand, perhaps had some inkling that the Istari were something else, but beyond that they wouldn't be sure, unless they had a deeper understanding like Elrond, Galadriel and even Glorfindel. Círdan himself knew because he was there at the Havens when the Istari arrived, even knowing that they came from Valinor, combined with his knowledge it makes sense he came to the (right) conclusion that the Istari were in fact Maiar.
To everyone else, they were just the "Wizards", another race in Middle-earth.
Addressing your quote:
[...] someone of a race against which we would never have dared to raise our hand.
The actual quote is:
'No, Sam!' said Frodo. 'Do not kill him even now. For he has not hurt me. And in any case I do not wish him to be slain in this evil mood. He was great once, of a noble kind that we should not dare to raise out hands against.'
The Lord of the Rings: The Return of the King, Book VI, Chapter VIII: The Scouring of the Shire
The Istari were known as Wizards to everyone in Middle-earth.
The term Wizard here refers to a separate race. In Middle-earth, there are Men, Elves, Hobbits, Dwarves and Orcs. "Wizard" to the folk of Middle-earth would fall under that category of "races".
To them, Wizard doesn't equal Maia. As aforementioned, no one except Elrond, Círdan, and Galadriel knew that the Wizards were actually Maiar. What people knew of Wizards were just that 1) They came from Valinor 2) They were of a different race. Both Barliman Butterbur and Denethor would have treated Gandalf differently had they known he was an angel of sorts. But they didn't. They only knew him as a Wizard, someone from Valinor sent to Middle-earth to help in the war against Sauron.
Same goes for Frodo (and Bilbo) I do not believe Frodo knew exactly that Gandalf was a Maia, just that he was of a nobler race than the rest. Frodo and Bilbo are Ring-bearers, and have greater insight, compared to Non Ring-bearers, in perceiving the things around them. This is evidently seen when Frodo notices Galadriel's ring, and isn't surprised either when Gandalf openly displays his ring at the end. They may not have known Gandalf was a Maia, but they at least knew he was of a more supreme race of being, because that's what Wizards were.
With this in mind, you could say that Bilbo and Frodo learnt that Gandalf was a "Wizard" from the start. By that time in the Third Age it would be common knowledge of what Wizards were: a supernatural race present in Middle-earth. But no one would be able to make the connection that the Wizards were in fact Maiar, or of the same race as Sauron, because they didn't know enough about the beings residing in Valinor.
And so Frodo and Bilbo never learn this, until they themselves arrive in Valinor at the end, whereas it's almost certain Gandalf would have told his friends more about himself by then. (Hat-tip to Buzz in the comments).
I will leave you with this quote, courtesy of Gildor.
"Do not meddle in the affairs of wizards, for they are subtle and quick to anger."