For classical, I'd start with a broad survey of stuff, and then narrow down on your favorite period or style or ensemble. Here's a very abbreviated, very personal list, slanted towards things that are very popular and in decent sound, so it will leave many things out:
Baroque: Bach: Brandenburg concerti (La Stravaganza), various piano pieces (Goldberg Variations, Well-Tempered Clavier, etc. Glenn Gould is my favorite), Mass in B minor (Gardiner). Vivaldi: Four Seasons: overplayed, but essential for you to know. I like Biondi's earlier recording, but either one of his is fine.
Classical: Mozart: various opera overtures (Marriage of Figaro, Magic Flute, Escape from the Seraglio). No favorites, but Gardiner or Marriner are safe choices. His piano concerti (try No. 21 whose middle movement you will surely recognize) and piano sonatas are also fun (avoid Gould unless you're into freak shows). Haydn: cello concerti. I like Wispelwey on Channel Classics. I'm not a big fan of this period, so maybe someone can suggest more stuff.
Romantic: Beethoven: all his symphonies, but I'd start with 5. 9's last movement is very recognizable. Everyone has their favorite. Try Gardiner or Zinman for more progressive readings, or Karajan 1963 for a more conventional approach. All his piano concerti, but I'm partial to 1, 2, and 4. I like Gould's 1 and 2, especially for the crazy cadenza he made for 1. Vogt/Rattle offer a modern recording of that cadenza. His piano sonatas are also very fine. There are lots of good recordings out there. The Naxos recordings aren't too bad, and are really cheap. I also like Gardiner's Missa Solemnis.
Brahms is another important Romantic. I really like his Intermezzi, which are these very personal, introspective piano pieces he wrote. Radu Lupu is a good start here. I'm not a big fan of his symphonic output, so someone else will have to help you out here.
In the same time period, but straddling the Romantic/Classical period a bit is Mendelssohn. I'd start with his Octet and his incidental music to A Midsummer Night's Dream, and maybe his Italian Symphony (no. 4). There are many multi-CD sets with pair all of these together. Kubelik's is one my favorites, but Mackerras is also very good.
I'll leave Chopin to the pianophiles. Very important, very beautiful music, but I can never keep their numbers and names straight.
Mahler is another important composer, but it may be too much for people new to classical music, because his works are all mostly very long. But they have this huge, epic, movie-like scope where he tries to bring every aspect of life into his music. It's big, melodramatic, and has to be played all out to make any sense. I'd start with his various songs like the Wayfarer Songs or the Ruckert Lieder. I like the Telarc recordings with Lopez-Cobos and Schmidt. Thomas Hampson is always a safe choice for lieder. If you want to start with his symphonies, I'd recommend 1 or 4, then maybe 2, 5, 3, 8, 9, 6, and 7, but some people find different ways into the music, and they are all worth hearing many times. Michael Tilson Thomas and the San Francisco Symphony are almost always safe choices, as is Bernstein, but Mahler fans argue over things like this, as both MTT and Bernstein represent the Dionysian branch of Mahler interpretation, and some people prefer the Apollonian side of stuff (Bertini, Horenstein, etc.).
Tchaikovsky writes very dramatic, sometimes overwrought, music. I like all his ballet music and symphonies. MTT and the SFSO have a DVD where they break down the performance of the 4th symphony that would be a great thing for someone new to classical music, along with an actual (very fine) performance of the symphony itself.
Some of the 20th century people you should know include Stravinsky (Rite of Spring, Petrushka, Firebird, his violin concerto, Agon, Symphony in C are some of his interesting stuff), Prokoviev (symphony no. 5, piano sonatas like no. 7, his ballet music like Romeo and Juliet as well as his violin concerti).
If you want to hear where movie music came from, start with Mahler and Tchaikovsky, and then go to Korngold. His violin concerto is like a little prototype for today's movie music.
There are lots of people I haven't mentioned, like Ravel, Debussy, Shostakovich, but this post is pretty darn long already. Try some of the suggestions out, let us know what you like, and we can narrow it down.