Luthor is a given. He's as big a part of the Superman-universe as Lois.
But I dont want him to be the main villain. At least not at first. I think he should be operating in the shadows in the first film and only slowly should we learn about him and who he is. Maybe we shouldn't even hear him by name until the end of the first movie.
Like I said, he shouldn't be the main villain as such, but I'd like to see him pull all the strings that eventually would lead to Superman's demise in the second movie or so, revealing him to be the main-villain after all.
Luthor should definitely be in the first installment, but only serve as a chancellor/emperor Palpatine sort of role.
As for a main-villain, on one hand if it's an origin-movie I'd like to see, and that would probably make the most sense, that simply mankind would be the villain, the biggest threat to Superman and his place in this world. That would seem like the most realistic approach, especially with Nolan pulling strings. And Luthor could plot against Superman using the people.
But on the other hand, I also very much think that's it's looooong overdue that we see some real "super vs super" in a Superman-movie. I'm thinking otherworldly arse-kicking here, Matrix Revolutions-times100-style arse-kicking.
But introducing that kinda foe would maybe seem rushed and too much for a first installment origin-movie. But in a Superman-movie in general, my picks would be either Brainiac, Apocalypse or Darkseid with Doomsday only serving as a henchman of sorts. Maybe Luthor could somehow be combined with Metallo in future movies.
The main-villain for the Superman reboot is a tough one IMO.