I don't think anyone mentioned Shostakovich's 10th Symphony in all the recommendations above...personally, thats how I started with Shostakovich. It has the mix of grim misery and brooding, wild fantastical energy (the 'Stalin' movement), and the quirky tunes and orchestration that I associate with him as an orchestral composer. I own the Haitink disc (probably mid price by now), but there are many fine recording of this.
I also like many of the other symphonies alot, my favorites being 1,4,5,6,7,8,10,15. I just bought the Barshai set mentioned above, and it really is astonishing value ($38 in the local Tower Records, and you can get it for around that price or slightly less through amazon.com marketplace sellers). Especially good value considering Barshai's links with the composer, and the good quality of the sound and performances, its an incredible bargain. In addition, for me at least, it takes away the financial risk of buying a complete set that includes all those other symphonies (e.g. #2) that are much more 'politically correct' for the time and for me at least much less artistically rewarding.
Ian