I don't think I really need to explain the story behind Gordon, he doesn't need one. The fact that he was mute really endeared me to him, the unspoken word is more powerful than the spoken one sometimes. Gordon's unspoken one is being a hero with an interesting arsenal that contains all the standby weapons (pistol, shotgun, bigger pistol, smg) as well as a few originals (gravity gun, the secondary on the pulse rifle), a simple but powerful backstory (Ph.D in physics from M.I.T., black mesa, Barney) and one hell of a goatee.
Mario jumps, drives cars, makes funny noises when he jumps and was originally in a game not even named for him, not to mention he was a carpenter, not a plumber, named jumpman then. Plus, he's based on a sterotype, which while it's sometimes funny, it gets old fast.