I recommend Barenboim's first (1960s) recording of the Beethoven piano sonata cycle as a start for piano music. Also his recordings of the Brahms piano concertos. Both are very cheap these days. And the late Schubert sonatas, by Richard Goode, Alfred Brendel, or Stephen Kovacevich. For guitar, I highly recommend the recordings of Antigoni Goni, Franco Platino, Fabio Zanon, and Denis Azabagic on Naxos. I agree with an earlier poster that Bream's Albeniz/Granados disc is superb. Also check out David Russell, arguably the best classical guitarist in the world today, especially his Bach CD on Telarc and either of his Plays Baroque CD's. The earlier one, on GHA, has a recording of Handel's 7th Harpsichord Suite that will knock your socks off. The latter (on Telarc) has a magnificent transcription of a suite by Lloieillet, an French contemporary of Bach. Williams' early recording of the Bach Lute Suites is still the best, IMHO. A wonderful disc too is Ramirez' Barrios disc on Deutsche Gramophone.
For violin music, I cannot recommend highly enough the wonderful Sibelius Violin Concerto. I love the Francescatti recording, but Heifetz and Kremer both have great renditions as well. Don't go Perlman on this one, but he's great for Tchaikovsky, Mendelssohn, and other romantics. Anything by Isaac Stern is awesome. Check out his old (1970s) recording of the Bartok sonatas. Fantastic.
For symphonies, I say start with Karajan's Beethoven cycle, and Klemperer's Brahms. Throw in Tchaikovsky's 4-6, with Temirnekov, Mozart 35-41 with Karajan or many others, and don't forget Bruckner. Karajan's recording of the 8th is possibly my favorite classical CD. Tintner's Naxos recordings are very good, and cheap. For Mahler, try Bernstein -- very idiosyncratic, but great. I agree with the earlier posters that Michael Tilson Thomas is good for Mahler as well. In fact, he's better than good for anything. Try, for example, his Villa-Lobos CD.
I'm out of space and didn't even get to chamber music. Well, happy discovering. JJ