1. Always introduce them first.
Nothing is worst for the reader than a character who is shoved in the story. Hey, it might work out fine but if you don't properly introduce him into the story, it might get hectic a bit further down the line. Now the way to do this, is to always have a scene that basically shows a bit of his personality and story as well. Start up a rumor upon his arrival, have them challenge the best, or bully the weak (in writing, please don't do this).
For example, let's say we want to introduce a bad ass character named "Flowers" -see the conflict at the very beginning? Bad ass conflicts with Flowers, so this should be a piece of cake (no pun intended... and this has nothing to do with the fact that I'm hungry)! Upon his arrival in the world or the place that the protagonist is, have them cause a stir, no one knows how to deal with this character who simply oozes badassry. Have them wear a top hat, and whenever they say something clever they flick it a bit.
Now, let's say this takes place in a tavern or an inn, and there is a fight. A bandit is bullying an old man, and every one just plays along and is laughing at this, to which Flowers intervenes, he flicks his top hat and says "My, what have we here? A bandit who knows no honor and good manners; what a surprise".
How does the bandit respond? By throwing a fist at our own Mr. Flowers, who quickly dodges, hold his arm and twists it, pushing him to the ground. Mr Flowers smirks and then twists even harder. "Would you like I teach you some?" he says as he glazes into the old man and winks at him.
"Who are you?" The old man asks, stuttering and nervous for some reason.
"Captain Flowers, at your service." he says as he loosened his grip on the bandit, and makes his way towards the exit.
"You're a Pirate? Here? I'm afraid you are in for trouble for assisting me . . . you see this place is ravaged by the likes of him," the old man says, pointing at the bandit.
"I know. I'm counting on it," Flowers says before he disappears.
Now, look at what we achieved with this short little scene that introduced a character that is simply too big to ignore as part of the scenery, we have established that he is the captain of a Pirate Crew, and that although he makes a living off of stealing ships and other... piracy things, he doesn't tolerate bandits -a thing that has apparently pushed him to come to a place where its full of them.
The reader will wonder about the goals of Mr. Flowers, why did he come here, and why the hell is his name so funny.
2. No character speaks the same.
This is a bit obvious, a character must have a unique tone to him, the way he says the letter "R" for example, and contrary to popular belief, dialog needs not to be perfect. "A charcatere, might speak however he desires, and is allowed to make mitsakes -I did that on purpose-" though don't think this is an excuse for bad grammar, it is literally quite the opposite. A Pirate for example would go like "Aye Captain, I be seeing a big and pretty island next to me eyes!" and the Captain could punch him straight in the face "why don't you speak like a normal person?" well, normal is boring.
Think of real individuals that you meet on a daily basis, although they speak the same language, none have the same backstory. Thus, a character must always be driven by a motivation. Something he lacks that he is after... whether that is revenge, power, lust or greed is up to you to decide, but seriously think about the key characteristics that differentiate your best friend from the rest and build it up from there.
3. How about you do an arc for each main character?
Seriously, you can do this as a subplot where they need to go back to the character's roots or home town just to figure out what went wrong/right in their life and try to see things from their perspective. It's a great way to add depth and weight to your book because the more time you spend flushing out the characters, the tougher it is for your readers when you kill them! Um... Sorry, reflexes...
By the time I finish properly introducing my characters, I'll sometimes be at the 40K mark depending on what I'm writing, but in the case of my current WIP, I did a character arc halfway through the book while shrouding her in mystery. Even her damn name changed everything for the protagonist. You can take your time with this really, but if you want to have that human connection to establish, readers have to know someone's why before they understand the how.
I've rambled quite enough, so if you got any questions on this, shoot me an email or find me on Twitter (where I'm most active) @infrangilis or you could just leave a comment here! I promise I'll respond, even if you tweet "The Penguin Overlord is watching you." at me. No but really, don't tweet that please.
Until next time,