Lots and lots of good stuff already listed here. (Certainly enough to make me either go broke or run out of space for CDs, whatever comes first.) Let me add my $.02:
Jazz
I must admit I have a weak spot for contemporary Norwegian jazz - a web search should quickly turn up folks like E.S.T and Nils Petter Molvær, or Jan Garbarek of course.
Classical
If you're after Beethoven's 5th and 7th, you could do worse than with the Vienna Philharmonic Orchestra under Carlos Kleiber. (I guess most people who are into Beethoven already have one version or another; you can get it as audio CD, hybrid SACD or DVD-A.)
Pop
Kate Bush - The Dreaming, Hounds of Love (actually most of her albums are well worth having, save for maybe the Red Shoes)
Phil Collins - Face Value
Talk Talk - Spirit of Eden remastered (not sure whether that one would make my list for a desert island, but a peculiar, melancholic record it most certainly is)
I'll second Mike Oldfield - Amarok (goes well with cans), as well as something from Captain Beefheart.