I changed my mind somewhat.
I now think Lucario is the best beginner character. He is well rounded and pretty simple, and doesn't really encourage spamming (AS I know, but its not as spammy as Pit's arrows or Kirby's Rock/Cutter).
I don't like Kirby as a beginner character because it encourages them to just keep Jump+Rock spam, or spam the Cutter. He is pretty laid back though, so if I guess he's okay if you convince them not to spam (something I have not accomplished

). His great recovery is a double-edged sword. It makes it less frustrating for them, but then when they move onto other characters they could get discouraged because their new recovery is not as simple or strong, then they end up never using anyone but Kirby. Sounds a little unlikely, but its happened to me before.
Pit is very easy to fall into the spam B + side B. And like someone pointed out earlier, his smashes are so quick that beginners might get used to C-Stick spamming and never get any better. His recovery is even better and more simple than Kirby's (though Pit's can be gimped) that similar problems could arise.
Meta Knight's specials are waaay too spammy, and his recovery is either too good or too frustrating, depending on whether or not they figure out how to glide

And I try to keep my household very Anti-Meta anyway.
Ike is alright. Very simple game-plan, but might be frustrating because of his slow attacks and poor recovery. Depends on what kind of play style they want.
Mario is well-rounded too with a variety of specials, I think he's a great starting character. The only problem is that he's not as effective as other characters which might make them frustrated later on, but in general he's a great starting point.
Whatever you do though, NOT OLIMAR, ICE CLIMBERS, OR DIDDY KONG.