I've got three omnibus books containing 9 total Warhammer 40,000 stories. Before I mention which ones I've got, which book would you recommend as a good place to start the series?
For a universe as rich as Warhammer 40k, I would recommend starting with a faction that you like the most. I'm assuming that since you grabbed 3 Omnibus books that you are into 40k at least to some extent. Personally I most enjoyed Gaunt's Ghost stories and Horus Heresy (no omnibus for Horus though I believe). But if you are into Eldar or Orcs or whatever, I would start with books that feature that faction. There are so many parallel stories going on that can be read in any order that I would not be concerned about hitting the story-order sweet spot. Enjoy!
Both Eisenhorn and The Horus Heresy books are aimed at introducing you to WH40K in some way.
This is a three book omnibus detailing different aspects of the Imperial Inquisition, who are like the 'Space Police' of the setting, and it really gives a flavour of the Grim Dark setting as whole. It covers all three orders of the inquisition (Xenos, Malleus, and Hereticus) as well as a few aliens (including Eldar), psychic powers, corruption and Space Marines.
The Horus Heresy
This series starts of with Horus Rising, and aims to lay down some of the assumed backstory behind the current Warhammer 40K universe. In essence these should be the first books you read, as they take place in the 31st millennium, 10 thousand years before the current storyline. So far I've only read the first book, but it explains things very well.
The only reason I'd be wary of trying to read all of the Horus Heresy is that it's currently on
18/ 24/49 books, unfinished and is being written by several authors so writing styles will vary. It also deals with the big picture of the WH40K background focusing on Space Marines, and doesn't give the same personal feel as Eisenhorn. It does however cover some aliens and corruption. It gets across the grand scale of the WH40K setting very well.
I'd also mention that all of the codices have the 'intro' description for the armies which goes a long way to filling out their part in the universe.
I'd suggest reading an overview of the setting before diving into the novels; the novels don't do a great job at that, as they are aimed primarily at extant fans of the tabletop games. Then pick any one omnibus and go from there.
You can often find older editions of the 40K rules inexpensively in the used bins at gaming stores, and the universe information there is much more easily digested, and allows finding your favored faction easier.
Just wanted to add that it's been suggested to start with the short story collection Let the Galaxy Burn as an introduction to the WH40k universe, and then follow your interests from there. I personally started with LtGB, then read Blood Ravens: The Dawn of War Omnibus, then from there on to Imperial Guard and Ultramarines novels. I did find it necessary at times to search online for background info that I was missing (e.g. the history and culture of the Eldar).
In reply to Gilles and Horus My personal recommendation is starting with a imperial guard series like gaunts ghosts or the lay chancers. They will give you a perspective of the average human. After that a space marine or a inquisition based series would be wise. The blood angels series is one i recommend due to its strong imagery and good story. After that it is up to you. The list i have is a expanded version of horus's answer minus the few i have not read.
Eisenhorn / Ravenor: Covers the Inquisition and the different Ordos. My personal favorite was the Ravenor series.
Ciaphas Cain: Hero of the Imperium / Ciaphas Cain: Defender of the Imperium by Sandy Mitchell: My one of my favorite series. The plot revolves around a hero of the Empire who believes himself to be a coward. Very light hearted compared to other series.
Ultramarines: A standard space marine series with themes of honor and duty. A great world but the characters are a little dry. The enemies are chaos and tyranids.
Grey Knights: I also enjoyed this series. Covering the grey knights and their wars against deamons. It covers the inquisition and its methods and it s relation to the grey knights.
Gaunt's Ghosts: an imperial guard series, among my friends it is either hated or loved. This series is considered the bread and butter of the imperial guard stories. The overall feel is that of band of brothers or another world war 2 series.
Blood Angels: A great story about a pair of brothers in the blood angel legion. I read the omnibus and i would recommend you do that also, there is a short story that reveals a another dimension the antagonist.
Last Chancers: This novel is an imperial guard novel that is about a penal legion and the main character Cage. Covering chaos, the tau, and 'nids. Truly a good series.
As several people have already recommended I think "Eisenhorn" is a fantastic Warhammer 40k book and is a pretty good place to start.
I also really enjoyed the Word Bearers series, which begins with "Dark Apostle", if you would like to dig into the corrupt world of Chaos Space Marines.
Over on my blog I have actually made a list of suggestions for new readers, which you might want to check out: Suggestions for new 40k Readers
I'd recommend getting onto the Warhammer 40k wikia site and researching a little bit into each faction (the first few paragraphs in an entry are usually an overview of the article involved).
You can do so by just searching a few of the major factions and reading part or all of the article that shows up. For instance, if you like humans, just search 'Imperium of man' and you will find an article that overviews the Human Empire and its internal factions as well as lists several of humanity's major enemies. Inside of this article is a list of major alien factions.
"Several alien species and dark forces (the Forces of Chaos, the Tyranids, the Eldar, the Dark Eldar, the Orks, the Tau, the Necrons, etc.) increasingly challenge the supremacy of the Imperium and humanity's predominant place in the galaxy".
From there just read about whatever you find most interesting. Horus Heresy for Chaos and Space Marines, the assorted Space Marine Omnibi for (obviously) Space Marines, etc.
People tend to find Space Marines most interesting, so I would recommend searching Space Marines as well, as most books are focused on Space Marines anyways.
I have only recently started to read Warhammer 40k. I have read the first two books in the Horus Heresy and although at first I didn't understand some things it then later clarifies. By half way through Horus Rising (the first one) I had a pretty firm grasp on the Warhammer 40k world and found the books easy to understand and read.
As someone who enjoyed playing the computer games, but not played the tabletop yet, these are my recommendations based on how I followed it.
First start with the Horus Heresy books; Horus Rising, False Gods etc. Then start Galaxy In Flames then The Flight of Eisenstein. After the first 2 books you would have what I believe is a reasonable grasp of the 40k universe with regards to the Imperium of Man v/s Chaos and why there are Traitor Legions within. You could then move on to discovering the other xenos aka Orks, Eldar etc.
The books are a pretty easy read, but don't let that put anyone off as they are quite politically focused intertwined with some good narrative.
However the downside, in the humblest of my opinions, is that I am starting to find the "Imperium of Man" is a bad organization. Especially with Horus being a Warmaster or have I read them wrong even before Heresy sets in. Of course Loken and his comrades are still good guys :). Maybe a spoiler there sorry :(
So go with Horus Heresy 1st 1-4 books if you're like me and only dabbled in the periphery of W40k.
I've fiddled about the edges of WH40K for years, then a buddy dumped a bunch of books on me, mostly in the middle of various series. What I can do at this point is recommend anything by Dan Abnett or Sandy Mitchell. Neither is in any danger of winning a Hugo, let alone a Nebula, but both have the hang if the "ripping good yarn". One thing that sets them apart is that they have each modelled a series on an extant historical fiction, adapting it to the WH40K milieu. Abnett has the Gaunt's Ghosts series, based on the "Sharpe's..." series (wot got Sean Bean his start), and Mitchell basing Ciaphas Cain, HERO OF THE IMPERIUM, on McDonald's "Flashman" series, which is essentially Italy a deconstruction of Sharpe. Now, I've read some Abnett, but none of Gaunt, yet. High 9n my list based on multiple recommendations, though. I can recommend Cain without reservation. 3/4 through the first omnibus, and it's both well written and spot on the setting, and a laugh riot.
Those more versed than I: is there a Hornblower or Aubrey/Maturin pastiche out there?