Felon said:
Pick an infamous character actor to play the villain (and I'm not certain that the Red Skull would be ideal as that villain).
To be honest, I'm not certain he'd be the best choice either, but as far as iconic Captain America villains go, his Rogues Gallery isn't exactly the most interesting or colorful. He's always been so closely tied to the Avengers that it's kind of hard to find someone to match him up against on his own, IMO.
I could possibly see something like using Kang and playing with the whole "Man Out of Time" notion, what it means to be the embodiment of the American Dream (as a concept that exists in a timeless fashion from the trends of the moment in Present/Past/Future America), even though Kang himself is more of an Avengers villain.
Otherwise, what do you have? Faustus, but he doesn't provide much in terms of a physical challenge to Cap. Arnim Zola, whose backstory is far more complicated than it's probably worth. Baron Zemo (either one), but if you use Heinrich, you might as well use the Red Skull. Helmut could be interesting, though, if you use Heinrich in the WWII part of the story and Helmut in the present.
Flag-Smasher, possibly, as Cap vs. the terrorist Ultimatum organization. Or Viper, possibly.
Can't really think of anyone else offhand that could really do the movie justice though.