Well, of the options available I'd definitely want to see Brainiac. And I want the Brainiac from S:TAS--with some of the Geoff Johns creepiness thrown in. There is no other Brainiac to me.
I'm with the general consensus that Darkside should be saved for number three, four, or Justice League.
But I want to make a case for Lex Luthor.
Lex Luthor is one of the greatest villains in the history of Supervillains--the fact that he's just a normal guy but occupies near the top spot in most polls attests to this.
Most times he's portrayed as an easily beaten, campy mad scientist. I loved Gene Hackman's portrayal of Lex Luthor, but it seems people can't get that version out of their heads.
Lex Luthor is a genius master-manipulator who plans several steps ahead of everyone else, untouchable by the law and has built an empire to rival anyone's in history. He's a complex individual who's battles with Superman aren't just about a hero and a villain, but the nature of a hero and good and evil and if those things truly exist.
Just like Batman Begins had Ras as the main villain before setting up Joker in TDK where we really got a dark examination of the two arch-rivals and the nature of heroism--I think that the sequel to MOS should do the same thing with Zod and Lex Luthor--with Metallo, or Metallo and Parasite (and maybe Toyman) providing the muscle for Superman's fights--until Lex Luthor steps into the power suit to take on Supes in the final showdown.
But that's just me.