I think the villian needs to be someone you wouldnt normally expect. Its all well to say Apocaylpse, Sinister, Sentinals because there the more famous characters but if we learnt anything from x-men 1 to wolverine that less popular characters like Stryker, Worthington Cnr, Dr.Kavito Rao... could all prove to be quiet more impressive.
For this i figure there is only one logical conclusion to who the villian should be.
i see first class as being a bit like revenge of the sith, were as you have a good guy turned bad, influenced by someone/thing that enters a new form of belief.
See initally we know that Magneto will go from good to bad so he is going to be the anikin skywalker of the movie, so we need an empiorer...and for that character i have one mutant in mind.
THE HIGH EVOLUTIONARY...
Here is my reasoning for this character.
1. The High Evolutionary was a scientist who was taught the art of genetic manipulation from Dr.Milbury an alterego of Dr.Nathaniel Essex, aka Mr Sinister.
2. Magneto is not a scientist, and thus would not be able to create the machine used in x-men 1, however High Evolutionary could create such a device.
3. Victor Creed went from fingers of a bag lady to you owe me a scream - which could be explained by The High Evolutionary's experiments to make him more abidiant.
4. He could easily be worked into the whole weapon x saga which has pretty much lead all four movies.
5. The High Evolutionary is a one off character that could broaden the x-men universe. For example he comes from Wundagor where Magnetos children are, The whole connection to Mr.Sinister could mean Sinister plays a future role in say X-Men 4 to 6.
6. The High Evoltionary is a single story, meaning you could use him for First Class and kill him off without wanted him to return. But his role would have set the whole mythos of the rest of the movies.
In my oppinion, i think The High Evoltionary would be great but you would need a brilliant actor to play him, id say Gary Oldman...