I'd definitely go with Stephen Graham. As you say, Graham had five seasons to perfect the character, grow with it, and show the transformation of small time guy to the biggest gangster in the world (or better said, the US). With The Untouchables DeNiro is already there. That said, DeNiro's performance was quite good. How about Paul Muni or Al Pacino as "Scarface"? Yeah, Tony Montana isn't Capone in name, but for all intents and purposes, he pretty much is.