Where is the correct place to put the "is"? I speak several languages and get confused when switching from one to the other.
In "he is truly great", truly modifies the adjective great, adding emphasis or allowing that he is more great than some other things that are also great.
In "he truly is great", truly modifies is and so argues against any doubt that he is great. "Truly he is great" would be equivalent. It's not a common usage any more, but it has some biblical uses that keep it current (or John Wayne in "The Greatest Story Ever Told" for those who watch more than they read).
Grammatically, either works and they are almost, but not quite, logically identical. If it is a true statement that he is great, then it is true that he is great. If there is a special degree of verity associated with his greatness, then he is truly great. "He is truly great," is almost certainly what you mean. It is idiomatically stronger. You might want to compare the two constructions here: https://books.google.com/ngrams
Both are correct, but have slightly different meanings.
"Truly" is an adverb, and thus can modify a a verb, adjective or other adverb.
In the first example, "truly" is modifying "is" (a verb). Whereas in the second example, it modifies "great".
So for the first one, his being great is verified as being true, wheras the second one verifies his greatness itself as being true.