This was a problem (that) he had to face.
I find it a little odd (that) you don't get out much.
Are these two that-omission situations the same (e.g. regarding to parts of speech)? Why or why not?
This was a problem (that) he had to face.
I find it a little odd (that) you don't get out much.
Are these two that-omission situations the same (e.g. regarding to parts of speech)? Why or why not?
Right, as you point out in the comment, the first one is in relation to a noun. It is a relative clause modifying a noun: This was a problem [that he had to face] (which implies He had to face a problem). "That" is completely optional in this relative clause.
In the second sentence I would say "that you don't get out much" is a clause functioning as a nominal with it-extraposition. Compare I find that you don't get out much (to be) a little odd—"that" is mandatory here. Omitting "that" as in I find it a little odd you don't get out much may be more informal.
In either case, 'that' is not required. They are the same for omitting 'that'.
I don't know why however from the years of writing I have done, I know that you don't need 'That'.
However, I would say that not omitting it is not too bad. It makes sense but makes the sentences wordier.