The word "Orthodox" is ambiguous. Technically, it is a sociological grouping. Because in practice, that group is of people trying to observe classical notions of halakhah, we think of "Orthodox" as the set of Torah observant people, or sometimes, the community / communities of Torah observant people.
(There is a gap there I want to point out: There is more to following the Torah than following the kinds of halakhos more readily codifiable in a Shulchan Arukh. For example, hilkhos dei'os / chovos halevavos -- laws of character refinement and attitude. Laws of general disposions toward people that don't fit into a finite list of specific actions, etc... One might argue that due to the self-definition of Conservative and Reform, Orthodox ended up being defined by only a subset of following the Torah -- those laws whose observance specifically depend on accepting classical halachic reasoning. And thus, it is quite possible to be Orthodox by observing the black-letter law, and yet not be fully Torah observant; in fact, to miss the very parts of the Torah that define the forest rather than the trees! At least, for some usages of the word Orthodox.)
So, breaking down your question into various uses of the word Orthodox.
Is there such a thing as too observant! Never.
Is there such a thing as choosing too many observances that don't fit in sociologically? Of course. Along these lines, I would include your husband's black fedora, which is a uniform for identifying with a community that is different than your synagogue's. Not "too Orthodox" but "too yeshivish". If he feels there is a halachic obligation to wear two head coverings when praying, there are socially accepted hats that wouldn't be self-excluding. Same observance, different sociology.
In contrast, their objection to your covering your hair doesn't sound like it's about social queues that are separable from the actual observance of the halakhah. Too Torah observant? Never! The problem is theirs, not yours.
There is an area of overlap. What if there are mutiple equally valid interpretations of halakhah? On the one hand, one might feel their more stringent interpretation is being more correct; why not continue to cover all their basis. On the other hand, if it causes division and animosity, it may be wrong for that reason alone. There is a reason why there is supposed to be a notion of a minhag hamaqom, the local place's community custom. Today the world shrunk enough and we've become too mobile for the concept to work too well. But if your pactice is causing friction... You'll need to consult a competant halachic decisor. Depending on the case, the specifics of the ruling you're following might warrant not switching, or the notion of mihnhag hamaqom might mean that you're doing something wrong by not switching.
Last, off topic, but I feel a need to express berakhos for best of success (hatzlakhah rabba) for settling into the new community. Clearly you are now among people who are culturally very different than you, and I presume you want to have friends in your new neighborhood. Since it has evidently been proving to be a tough transition for you, I feel that remaining with Mi Yodea's usual formality and omitting the berakhah would be wrong. Keeping in mind the difference between cultural norms and halachic norms, so that you can adapt more culturally without watering down observance might help, but asking for G-d's Aid is always appropriate.
(H/T @Monica Cellio who talked me into expanding my comment into an answer. I hope neither of us end up regretting it.)
Is there really such a thing as being too orthodox?
and b)I never thought I would have to uncover myself to fit in at a synagogue. What should I do?
The latter seems primarily opinion based. There is no such thing as a bad question, but there is such a thing as a question that is not strictly on topic here.