I'd love to see it open with Supes already in the middle of a fight with a throw away villain like Metallo for instance. You could have Metallo being sent by Luthor in yet another failed attempt by Lex at killing Superman. Metallo loses after about a 5 minute tussel. A few cars thrown, a few punches, etc.
Lex is furious, yet again
Then Brainiac arrives. He detected the F.O.S., and the kryptonarian tech it contains, from space. He concludes that Lex is the most intelligent human on the planet, and he also has a hatred for Kryptonarians as well. He makes contact with Lex.
Brainiac would be just as strong as Superman, if not more so.
You could show flashback scenes of Krypton when Brainiac explains to Lex where he came from. Brainiac would have been Krypton's super computer and protector, untill he went rogue. You could go back and show hundreds of yrs of Kryptonarian history, all up to the point that Jor-el launched little Kal-el into space.