No one mentioned Zelda as a cheap character?
She isn't so bad, but when she turns into Shiek, gg, gl, hf. Shiek requires little to no skill and can always get back on the board (morph back into Zelda while trying to get on, and you teleport back on top every time).
Fox is also really cheap, but I pretty much only use the sword characters and their reach > his quickness.
In fact, that's why I use the sword guys. Yeah, they all have long reach, but how else am I gonna keep all the little short shits away from me? My friends have always been better with the quick characters than I have (see: Guilty Gear's Chipp and Garou: Mark of the Wolf's Rock Howard) so I tend to get good with the ranged characters.
I can't believe no one mentioned Mario. I LOVE MARIO. He is so fun to play as, and in 1v1 situations, is unstoppable if you know how to work him. His smash attack has that little fire poof at the tip of his hands, so even if they parry or hit you, you'll hit them, and his cape is ungodly, especially against characters that have moves that are more horizontal than vertical to return to the map (Donky Kong, Bowser, Luigi, Captain Falcon/Ganondorf, etc.). Even though I lose with him a lot, I just have so much fun, that I don't even notice.
As for Kirby: Kirby sucks in SSB:M. He was awesome in the original SSB, but I honestly don't think he's any good in Melee. Absolutely NO range and he's not very quick. He's pretty decent if Samus is in the fight, but then again, why not just use Samus?
Oh, and Samus is a rediculously cheap character. You guys need to play my best friend. You will lose. I guarantee it. Back in high school with the first Super Smash Bros, kids would be saying all the time how good they were, then me and my friend (who never really gloated because we just played with my other brothers and a couple other close friends) would go to their houses and win 3 v 1 matches against these guys. We're pretty good.