Rav Hirsch says they were not embarrassed as such, but they were afraid of having now entered a state in which they can feel shame. This feeling meant that they were afraid of being in the presence of Hashem.
Rashi points out that it was not physical nakedness, but moral and spiritual, having disobeyed the one mitzvah that they had. Thus, even with the aprons they still felt naked (see below from Rav Hirsch). In fact according to this, even if they had been completely covered, head to toe, they still would have felt naked when Hashem came.
and they knew that they were naked: Even a blind man knows when he is naked! What then is the meaning of “and they knew that they were
naked” ? They had one commandment in their possession, and they became
denuded of it.
Additionally, when they heard Hashem, they were not embarrassed because of their nakedness, they were afraid
וַיֹּ֕אמֶר אֶת־קֹֽלְךָ֥ שָׁמַ֖עְתִּי בַּגָּ֑ן וָֽאִירָ֛א כִּֽי־עֵירֹ֥ם
And he said, "I heard Your voice in the garden, and I was afraid
because I am naked; so I hid."
Rav Hirsch says:
This being afraid, not ashamed, proves that the consciousness of being
naked has to be taken in the sense of its moral reason, as explained
above in V.7. Not because of his body being naked, but because he no
longer dared let his naked body be seen, was what made him afraid for
Thus, he would have been afraid no matter what he was wearing and no matter how covered up he might have been. It was not a matter of denying that he had eaten, but the consciousness of having disobeyed and feeling the results of that.
Rav Hirsch in verse 7 says
But the consciousness of being naked is the consciousness that
something is visible that should not be so. This is the feeling of
shame, which as indicated above, has its roots in the consciousness of
a person of the real calling of Man. As long as Man stands completely
in the service of his Hashem, he is not to be ashamed of any part of
his body. Even the bodily lures and attractions are pure and godly as
long as they submit themselves as means for Hashem's holy purposes.
But when this condition is not entirely there we certainly should be
ashamed of displaying them. This shame awakes the voice within us,
which is intimately connected with the conscience, and reminds us that
we are not to be animals.