One of the best ways to start is to figure out what sort of conflict the protagonist is up against since we (and fictional characters) are often defined by our struggles (and lack thereof).
Is he (or she) up against another character (
man vs. man), trying to survive the elements (
man vs. nature), dealing with an internal struggle (
man vs. himself), or some combination of the three? Think about what sort of attributes the protagonist will need in the end to overcome his conflicts.
Any good protagonist will grow over time, if not physically then at least mentally or often both (even characters who are insanely powerful to begin with, like Superman, grow throughout their stories). Think about the state your protagonist is in when the story starts and how he'll grow from that state to the state he'll be in when he has the attributes necessary to overcome his conflicts. Often in games, the "just along for the ride" hero Paul is speaking of is one with very little character growth. They pretty much plateau throughout the whole game.
When your protagonist is up against a villain he shouldn't be the polar opposite of the villain, he should share some of the villain's traits (and vice versa). The villain should be his dark mirror who illustrates the evil that the protagonist could potentially succumb to. Examples: Luke Skywalker vs. Darth Vader, Cloud vs. Sephiroth, Batman vs. The Joker, Cecil vs. Golbez, Squall vs. Seifer, Ryu vs. Akuma, etc.
They will often seem to be two different branches grown from the same tree. Batman and The Joker both grew from tragedy but where Batman tries to protect the innocent The Joker imperils them. Cloud and Sephiroth are both very cold and detached when the story begins, but Cloud becomes warmer and more friendly as the story progresses while Sephiroth grows colder and even more detached and ruthless. This branching allows you to explore two perspectives of an issue and can help avoid the bland one-dimensional "this guy is just evil" or "this guy is just good" stereotyping.
Ultimately the protagonist should have something (or some things) he stands for that drive his being. Most successful people are driven by some desire or need that pushes them out of their comfort zone and spurs them into action. Cloud, for example, is driven by a mixture of revenge, rivalry, and the need to protect the people he cares for (all the things Sephiroth is inciting or endangering). Having sincere convictions is what will allow a protagonist to find strength even in their weakest moments and keep them growing throughout the story.
One of the most overlooked, but often very beneficial, things you can do when creating a character (protagonist or antagonist) is draw out (or write out) some of their most basic, mundane behaviors. How does the character eat and drink (what kind of manners do they have)? How do they sit (slouched and relaxed, tense and readied, upright with good posture, etc.)? Do they have any dialog quirks ("I often end my sentences like this, ya know?") or body language habits (for example, they clench and unclench their fists repeatedly when speaking in a frustrated manner)? Sometimes it is the most minor of details that really stick in the mind and really round out the character for the player (or reader, viewer, whatever).
As for the looks, here's a few things to think about from the
character designs thread:
Community
