I don't think Brainiac being on Smallville will be a major issue. If this movie gets made and/or released in 2009, Smallville will probably be off the air. I'm assuming this will be, or should be the last season coming up.
Plus, the name Brainiac hasn't been used on the show at all. Casual or Smallville fans wouldn't know that Milton Fine is connected to Brainiac at all.
My ideas for featuring the Supes franchise villians:
SR2: Cadmus-Amanda Waller, Parasite, and Metallo (I would have Parasite and Metallo be Cadmus projects)
SR3: Milton Fine, Brainiac, and maybe Bizarro or Doomsday (Brainiac, working with Dr. Fine might develop either Bizarro or Doomsday in a plot to take out Superman)
SR4: Jax-Ur, Mala, Nam-Ek, Aethyr (Supes discovers there are more Kryptonians left alive. When he rescues these refugees/prisoners from Darkseid he begins to realize why they had been imprisoned in the first place. Tie the backstory into Superman's 5 year absence perhaps.)
SR5: Darkseid (Invades Earth to get revenge on Superman for defying him on Apokolips)
Superman has a strong enough rogue's gallery that the next movies don't need Luthor or Zod.