"He is a great man."
Translation:Он великий человек.
It seems that "великий" is the matter here. It implies "greatness" as in "a great deed" or "a great empire" (=glorious, powerful…). You could say "Он великий человек" about some hero or an otherwise famous (or even not famous) man who did something worthy of admiration. "He's a great guy" might be "Он славный парень" or "отличный" or just "хороший."
As a side note: When speaking about a woman, both "Она великий человек" and "Она великая женщина" sound fine to me.
One can only guess. :-) But I’m afraid that it might be because, strictly linguistically, when you say "он великий человек", you don’t need to specify that he is male ("Он великий мужчина" indeed sounds like he is great at being a male), while "она великая женщина" is something worth specifying. :-(
Unlike Ukrainian, in Russian you can't use instrumental with the present tense of «быть» (and the sentences with no verb are considered sentences the verb with «быть» omited). It works in past and in future, but not in present.
It could work if you change the verb, e.g. «Он явля́ется вели́ким челове́ком».