Straight Warhammer (Fantasy) and Warhammer 40K (Sci-Fi) are basically separate universes that share a lot of similar elements. I think 40K is way more interesting and original, but there still is a pretty rich written history for Warhammer. Really, the best thing fantasy has going for it are just interesting races. There are all sorts of ideas of how the universes could be connected, but none of them are officially recognized by Games-Workshop and, at best, tend to be like fan-fics.
Honestly, the best place to start is probably the rulebooks for the games. While you might not use them to play the game, they tend to have pretty excellent background sections that give you the general story and touch on most of the major points. They really do form the core of the universe and, without them, I sort of feel like you'd be missing the foundation which a lot of the novels seem to treat as prior knowledge. They're also just kind of fun to look at, sort of like how a D&D book might be. If you want to try a game, Dawn of War 2 does a good job of just showing the character and feel of major elements of 40K.
If you want books, Que's Ultramarines suggestion is good for the Space Marine side of things. It'll show more or less what the Space Marines are about in the best ways that I know of and, like Que said, is a good place to start since they're the most iconic element of 40K. If you want to go further into the universe and see how interesting it can get, go to the Eisenhorn series (this is probably the Inquisitor book Que mentioned). Like the Ultramarines stuff, it's collected into an Omnibus and gives you a fair amount of bang for your buck. Eisenhorn follows the career of an Inquisitor(something like the Spectors of Mass Effect, only far scarier) and it covers all sorts of things that are far too subtle for Space Marine stories. Usually, these series is cited as the best written of all the 40K stuff out there, so it's hard to go wrong with it if you're into sci-fi. If you want something more "fun," there's the Ciaphas Cain series (also in Omnibuses) which covers the career of an officer in the normal human armies. The Cain novels have a good sense of humor and, in a way, make fun of how absurd the universe can be. I'd say the Cain series is something like a love letter to Warhammer 40K and, therefore, might not be the best place to start but a good place to continue. There's the Heresy series as well, but they vary wildly in quality and I feel like they're really only worth your time if you've already got a bit of background info since they're all about filling in details of the major history events that are referenced constantly. They're not a good place to start, but fun if you really get into things. I haven't kept up with it, but the first few books were cool.
I haven't read any of the fantasy books (rulebook included), so I can't really help you there.
