As a 40k reader and on/off player of about 10 years, I'd seriously recommend you start with the "main timeline" stuff (i.e. the 40th millennium onwards), which contains stuff like The Gaunt's Ghosts Series, Eisenhorn (my personal favorite by far, but somewhat atypical as far as 40k novels go), Ravenor, etc. Also one of the best out there is Storm of Iron by Graham McNeill, which is basically one novel with the bad guys as main characters.
IMO, the reason you shouldn't start with the Horus Heresy series is that you really should understand the 40k main timeline stuff and universe to be able to fully appreciate the events of the 30th millennium (Horus Heresy series). The Emperor of Mankind, interred in an eternal coma on his Golden Throne, is worshiped as a God in the 40th millennium, the society has turned ultra-religious, and innovation and new technologies are feared (in general). You will enjoy the Heresy books a lot more if you have an understanding of the later developments of the Imperium of Man as things are a bit different between the time periods (apart from the constant warring that is

).
I would also recommend reading a wikipedia article about the heresy in general (
this seems pretty good) because it will give you the main timeline and events of the heresy. The HH books are extremely varied in topics and although they cover the "main events" of the Heresy, they often feature main characters than aren't the prominent figures in the history (for example, the Emperor himself, Horus, the Primarches, etc. are rarely seen in some of the earlier books) so it might be hard to fully appreciate them if you don't know the background.
The Heresy books are better read in chronological (or publishing) order. The 40th millennium stuff not so much, apart from reading an individual series in order, as different series occur around a time period of 1000 years.