Superman was not blessed with terrific enemies during the Golden Age. For various reasons (most likely Captain Marvel), Superman began to take on a more whimsical tone during the 1940s. Some of that may have been due to the limitations of story-telling for a character so overwhelming in his power that it became difficult to imagine him being seriously threatened. Remember, these were the days before Kryptonite.
He did have a few recurring villains, but all of them had something in common: They depended on guile and trickery: the Prankster, Toyman, and Wolfingham were all conmen at heart. Luthor was slightly different; he was a throwback to the mad scientist villains of the movie serials, but even he was usually behind the scenes until well into the story.
It was never quite explained why Luthor was so mad to destroy Superman; we were led to believe it was simply a mania. Then came Adventure #271. This was Luthor's second appearance in the 1960s in a comic mag, but at the time it was his first ever appearance chronologically going by Luthor's age, because he appeared in a Superboy story.
In the story, Superboy befriends the teenaged Lex (first time the given name is mentioned) and they become fast pals. But when Superboy rescues Luthor from a misguided science experiment, it is too late to save the young man's hair. Now we know why Lex Luthor is bald, and in an irrational outburst, he blames Superboy for the whole incident and vows revenge.
Luthor's character continued to evolve throughout the 1960s. In a memorable series, he became the hero of the planet Lexor. In Superman #164, Luthor decided to have a showdown with Superman, but smartly challenged the Man of Steel to a duel on a planet with a red sun. They started with a boxing match, which Superman won after a rope-a-dope strategy. Then they made their way into an alien city. Luthor was able to take advantage of his skill with machines and science to assist the aliens and was proclaimed a hero. When Superman comes along to continue their duel, Luthor initially wins, but then gives up. Why? Because he wants to help the people of the world who have adopted him to find water, but there is none on the planet. Only Superman can save them by sending a mountain of ice to the planet. In the end, Superman shows Luthor that the inhabitants of that planet have constructed a statue to him.
Luthor pays a brief visit to Lexor in Superman #167, in which he meets an attractive woman named Tharla. When he returns to Lexor the following issue, Tharla has changed her name to Ardora. He continues to experiment with the alien machines while wooing Ardora. Meanwhile Superman arrives and finds himself oddly compelled to steal rainbow crystals that the citizens of Lexor are presenting to their benefactor.
Lex discovers a super-power producing ray, and decides to take a secret identity as the Defender. In a hilarious bit, Ardora suspects Luthor of being the Defender; echoes of Lois Lane! But although Lex captures Superman, once again he is convinced he must free the Man of Steel in order to save Lexor. The rainbow crystals turn out to have an effect on people, lowering their intelligence level.
But Lex cannot just let Superman go, so he creates some red Kryptonite that will steal Superman's powers temporarily and heads to Earth to capture his nemesis. By a fluke, Luthor is sent back into the past, to San Francisco 1906. He becomes the editor of the Daily Planet in that city. Superman finds out that Luthor's there via a "psycho-locater" built by the scientists of Kandor, but when he travels back in time, he somehow doesn't realize that his boss is Lex, under some muttonchop whiskers.
Lexor is barely mentioned in the second half of this story. Luthor is eventually caught, and Ardora is left wondering what happened to her boyfriend.
She finds out in Action 318-319. Luthor returns to Lexor after escaping prison. He is obsessed with the knowledge that Superman will eventually come after him. Sure enough, Superman finds him and during a fight, apparently accidentally kills Luthor. Superman is put on trial for his life. Fortunately, he is able to escape long enough to prove that Luthor had not died, that he'd just slipped into a temporary coma with the aid of a pill. Superman is set free, but Luthor remains behind on Lexor, still the hero of his world.
I was unable to locate the next adventure in the series, because the next time we see Lexor mentioned in Action #333, Luthor is in jail, further angered at Superman because he had revealed to Ardora that Lex was actually a famous criminal. Looking at the GCD for appearances of Luthor in the 1960s, we can see that Luthor appeared in Superman #173, #175 and #179 in between Action #319 and #333, as well as a couple appearances in Superboy and Adventure, and two in World's Finest, but none of these seem to be the story in question. Anybody know what I'm missing?
Update: Found it. In between the stories in Action #319 and #333, Luthor appears in Jimmy Olsen #87. He, Brainiac and the Legion of Super Villains get trapped on the Devil's Island of Space. Then, in Action #332, he escapes from that prison planet. Superman, realizing he may be hiding on Lexor, arranges with some scientists to be teleported to that planet for a five-minute period. While there, he accidently discovers a hiding place where Luthor has hidden mementos of his criminal exploits. Ardora discovers him and:
Interesting; shiny disks that contain lots of data. Of course, Ardora is horrified to learn that the man she loves is pure evil (although she seemed quite ready to murder Superman only a page before). But she still loves Lex despite his criminal past.
The rest of the story concern's Luthor's attempt to drive Superman crazy, by saving his life time after time. In the end, though, Superman figures out the diabolical plot. However Luthor escapes to Lexor with Brainiac, apparently just avoiding being hit by an object thrown by Superman. However, the object was not aimed at Luthor and Brainiac, but at Ardora:
This series does a good job of humanizing Luthor. The story of Ardora and Luthor was largely dropped after this, at least in the Silver Age, although it would appear again much later, as it turned out Ardora had borne Luthor a son.