Milch wanted Ed O'Neill, but HBO refused to build a big Western drama around a guy who was still best known as Al Bundy. Then Milch hired Powers Boothe, only Boothe got sick before the pilot filmed, and it was only then that McShane was hired. [source]

What could have been: Al Bundy as Al Swearengen on Deadwood.
What was: Al Bundy on John from Cincinnati.

Ed O'Neill almost played Sam Malone on Cheers too, and "Popeye" Doyle in a television adaptation of The French Connection.