Glencaer wrote:That being said, sometimes a few cliches aint SO bad

Agreed.
And sometimes a cliché can be a good starting point to a more fleshed out character. Take a stock, over-done character, and then start adding/changing things to make him unique.
Let's take your typical "super-warrior". You know the kind: big, strong, excellent fighting skills, lots of stamina, tough personality, possibly bearded.
Well, to make this basic "Sir Tough Hero" into something a bit more unique, a bit more special, we need to flesh him out, give him some details. One thing one can do is make him, despite his toughness, not really a big fan of fighting. He'll do it, and do it well, but he won't do it if not necessary. And you could maybe add a soft spot for kids. And maybe a little bit of a wild side when riled up.
Then you can flesh out his background. Nothing makes a character real so much as a background. Where does he come from? Is there a traumatic event in his past that he doesn't like to talk about? Who are his enemies?
And then....
Don't think too hard about it.
Just write the character, as best you know him, and see where things go. The character I've just described above is a sort of paraphrase of Sir Dractor. I didn't even know all that when I started. When I started, he was just a tough warrior type (a bit reckless) who happened to be a main character of mine. He certainly wasn't the very fully fleshed-out character he is now. Back then I couldn't have seen him vacationing in Drullen Bell, playing chess with Bjarn. I couldn't have seen him taking Luxus under his wing, or Thomas. I don't think I could have seen him surviving a hit from a catapult stone (I still don't know how it happened...).
Basically, what I'm trying to say is... get to know your character. Just let it flow, and see what quirks come up, or how he acts under the situations of the story. If you just go for what sounds good at the time, you may end up with a weird and/or awesome character.