Good list and I'm very ashamed to admit that I've not read a single book by Asimov *or* Heinlein. Well as soon as my Sony 505 shows up I'll just have to remedy that! Anyway, let's see if I can add something useful here.
Science Fiction
Frank Herbert - Dune (classic and well know for a good reason, though I didn't care for the rest of the Dune books.)
Alastair Reynolds - Pushing Ice (first of his books that I read. Great space opera with a fair amount of solid science thrown in)
Alastair Reynolds - Revelation Space / Redemption Ark / Absolution Gap (loved the series, but like most others thought the 3rd book was much weaker than the first two)
Tad Williams - The Otherland series (it's definitely not hard scifi, but I'd still say this is generally science fiction and good stuff)
Fantasy
J.R.R. Tolkien - The Lord of the Rings Trilogy (not for someone new to fantasy, but I feel it's needed on any Fantasy list!)
Tad Williams - Memory, Sorrow, and Thorn trilogy
Terry Brooks - Shannara series of books (this is more for someone new to fantasy I feel as it's a little light for me now)
That's what pops into mind quickly in addition to your list. I'll make notes as more people add items here for what I need to be reading.