definitely upping Ian McShane in Deadwood--the scene where he stares down Calamity Jane to get to the little girl is one of the best moments in the show.
How about Steve Buscemi as Mr. Shh in Things to Do in Denver When You're Dead? Technically an assassin, but an assassin for the mob nonetheless.
Harvey Keitel's The Wolf from Pulp Fiction. With this character, it was the fact that he was so precise and understated that made him scary -- he would have absolutely no problem tossing you into the garbage compactor if he felt it was necessary or if you annoyed him.
David Carradine's Bill and Michael Parks' "Esteban" in "Kill Bill." What made them so scary for me was how quietly seductive they were. They were both so calm and personable, friendly and erudite, that you could easily be lulled into forgetting that they were vicious bastards who maim and kill for fun, profit, and thrill.
Terrence Stamp's "The Limey".
My roommate also suggests Edward G. Robinson in general, who was so good at conveying malevolence.
Hey @Lazarus99 - I immediately started thinking Jack Nicholson in Scorsese's The Departed. (I haven't gotten to see Infernal Liaisons yet but heard that was brilliant.) I once caught myself describing Nicholson's character in Departed as the Joker if he existed in real life. Heh. As it is, Nicholson's Departed character was based on a real Boston gang boss and apparently was true to form in how maniacal and ruthless he was.
Oh yeah and definitely Ledger's Joker was terrifying - it's just that I'm not sure it's so much the same when the excitement of watching an evil human-thing do his frightening best overtakes just how scared of him I feel. But the question is for scary, not for "holy crap, wow, he just slammed that stupid guy's head on a pencil! Holy shit!!" then again, when Ledger's Joker set about pitting Gotham against itself "just to watch it burn" that did chill me to the core....
I always liked Michael Caine in Mona Lisa. There's a scene where he just explodes at Bob Hoskins, says he want's "something, dirty, slimy, nasty, kinky" that is chilling. Hoskins reaction sells it, but Caine is fucking nasty in the kind of role you don't see him play much. Excellent film, too.
James Cagney - The Public Enemy and Angels With Dirty Faces Viggo Mortensen, Ed Harris and William Hurt all get equal billing for A History of Violence Gabriel Byrne and Albert Finney - Miller's Crossing
Chopper Reed isn't technically a gangster, He's a standover man, and generally is treated by the gangland community as public mental case number one, still, a genuinely terrifying man. I'd forgotten Terrence Stamp in the limey, and of course, Ben Kingsley as Don Logan. I've had the dubious pleasure of knowing someone with exactly the same degree of sociopathy as Don Logan, and quite frankly remembering it makes my guts curl.