The UK’s Guardian is running a series on 1000 Novels Everyone Must Read. Recently they’ve been listing fantasy, horror, and science fiction that fit in this vein. There’s lots of good suggestions in there. The British angle also broadens the horizon.
Obviously, given the breadth of the categories, and the difficulty of clean definitions, there’s a lot of room for argument. I’d definitely add John Brunner’s The Shockwave Rider. If Vernor Vinge’s True Names wasn’t a short story, I’d add that as well. Especially if they’re going to include something like Stephenson’s Snow Crash, which I always felt was overrated a bit due to a reliance on ethnic stereotyping and too much cleverness by half. Hiro Protagonist? Yeesh.