Costner uses the same tone of voice, the same inflection in his words, the same vapid stare, in every role. He was the only one in Robin Hood who was not in English character - probably because he could never have pulled it off. That indicates a lack of range. He is just like Tom Cruise - he bought the rights to these good movies and then fucked them up by casting himself.
I like Paxton. But when I see him I think of him as Hudson in Alien: "That's it man, game over man, game over!" Trivia fact: Bill Paxton is the only actor to have been killed by Alien, Predator and Terminator.