First appearing in Action Comics #23 (February 1940), Luthor was a mad scientist bent on world domination that used hypnotism to keep his lackeys in check. Later on in the month he also appeared in the Spring issue of Superman (#4) in two more stories. In each story, he tries to use his superior intellect to outwit Superman, of course failing every time.
All of these appearances show him as a red-headed scowling man of medium build in his late thirties or forties who employs bald, stockier henchmen, all of which look a lot like the Luthor of the 1950s and 1960s (as well as the original form of the Ultra-Humanite). It turns out that an artist for the Superman newspaper strip would accidentally confuse Luthor with one of his henchman and ever since, Luthor has been depicted as a bald man. When DC introduced the concept of a multiverse, the red-headed criminal scientist was considered the Luthor of Earth-2… because that would make things much clearer apparently. :-/
The trouble with that whole theory is that the Earth-2 Superman (Kal-L) worked for the Daily Star, and Action Comics #23 is the first time that Lois and Clark are working for the Daily Planet: