As stated, The Undertaker is pretty much the Giant Anti-Giant. Any giant, immovable sloth that has existed in the last 17 years in the WWE, has been destroyed by the Deadman (sans Vader, interesting).
The Big Show certainly isnt' as bad as Bundy, Gonzalez, Khali, Kamala, Berserker, etc.. etc.. That being said however, the Undertaker shoudl take this fairly easily. Outside of the Chokeslam from Hell on Raw back in 99, and the beat down he gave a worn down Undertaker after Hell in the Cell 2002, Show has had little success against the Deadman. The Undertaker handled him pretty easily all throughout 2002.
I see the deadman winning, and with one of his new lovely chokes.