I like this question..
To begin with, I agree that Douglas and Stewart would have fitted well because of their, as you put it, "underlying air of quiet simmering anger". I also think Randolph Scott would have been an obvious candidate. His work with Boetticher alone gives evidence of that. And also in the 'wrong age but right attitude' category would be Robert Mitchum. Not to forget Marlon Brando. I always thought he should have made more westerns, period.
Next category would be 'right age, wrong budget' in which I would include Paul Newman who also still had that simmering anger thing at that time and was good in everything he was in.
And lastly, 'right age, right budget, but never really did' category. Top of which would be Lee Marvin. He wasn't a really big budget star in the mid sixties and would have been perfect in these films. As would Henry Silva, who I know made one but could have been used so much more.
But the man I would most like to have seen in Spaghettis, at any time in his career, would have been Emilio Fernandez. Not a big star of course but all Wild Bunch fans will remember him as General Mapache where his greasy haired nastiness stole the screen from everyone. He would have been the bad guy to beat all bad guys in Spaghettis in my opinion. Of course, Fernando Sancho wouldn't have got so much work, but hey, it would have been worth it.