Personally, I think creating an "iconic character" is the entirely wrong goal. Instead, I think it's better to dig a little deeper:
what are you trying to do with the character? Look at some examples:
This is the Spy from TF2. I think someone mentioned this earlier in the thread, but TF2 was designed with a major emphasis on readability; characters' traits and abilities are supposed to be easily determined from their appearance. This guy is kind of scrawny, wearing a business suit in the middle of a battlefield, and carrying a knife. If you see him you're not supposed to run away, and this is clearly conveyed in his appearance. As a character, he accomplishes his purpose well.
Here's Sonic. Unlike the Spy above, it isn't really important for Sonic to be readable; the player learns right away that Sonic is way faster than he looks. Instead, Sonic is designed with a very strong visual style. He's basically two spheres stuck together. He runs around on loop-de-loops collecting rings. Look at those spherical trees in the background. The villain is just a sphere too, as are most the enemies. The whole game has this sort of recurring visual motif of spheres and circles, giving it a style that makes it easily recognizable when compared to other games.
Most people playing the game probably know almost nothing about Sonic as a character, and that's okay. They don't remember "a fast hedgehog, how original!", they remember the game and its visual style as a whole. Personally, I think the later games didn't catch on as well because they moved away from this strong visual style. This is also why games like Minecraft are so easily recognizable; the Minecraft "style" can be recognized in an instant.
Here's GLaDOS. You don't even see her until the end of the game, yet she is undeniably the most recognizable character from Portal - most people don't even know the protagonist's name. GLaDOS was specifically designed to provoke and taunt the player, being an interesting antagonist. What people remember about GLaDOS is her personality: her dry humor, strange promises, and eerie dialogue. She is very much an iconic character because of her writing.
These are just a few examples of pretty good characters, but I think they illustrate my point well. Sonic would not have gained much from making his character design "look" fast. The Spy would not have gained much from a more original personality. GLaDOS would not have gained much from looking similar to all the other characters in the game. Each of these character designs could be considered iconic, but they are really just accomplishing a very specific purpose. If you want to create an iconic character, I think you should just figure out the character's purpose and then streamline him to fill that role as elegantly as possible.
That's my take on it anyway.