From all i remember, it was Krajicek who gave Pete the most trouble and the record seems to confirm this. I also remember one of Pete's wins vs. Krajicek at the US Open and even then it was obvious how difficult a match-up it was for Sampras... Krajicek was a couple of points away from a 2-set lead.
Of course, at his best Krajicek was a monster to play against- huge serve, incredible net coverage and overall competent game. Pity he was often injured and never seemed to reach his max potential. Seems like a common theme for the really big guys in tennis