Alright, at this point, I've read everything except Uprising (I have it as part of the Archives, but never got around to reading it), so here's how I'd recommend each of the books:
Game to Book Adaptations - Liberty's Crusade and Queen of Blades
Decent reads, they flesh out a bit of the gaps in the first two episodes of StarCraft. Liberty's Crusade isn't too vital, it's mostly stuff you'll already be familiar with, but Queen of Blades gives Raynor's perspective of the second episode of StarCraft, and goes into detail with how he and the Raiders befriended Tassadar and Zeratul. All in all, I'd suggest skipping Liberty's Crusade, but reading Queen of Blades.
Ghost Saga - StarCraft Ghost: Nova, StarCraft Ghost: Spectres, and StarCraft: Ghost Academy
Nova is a great book; not without its flaws, but it gave a lot of personality to a character I expected to hate. Having played WoL before reading this novel, I didn't have high hopes for it (since Nova is quite shallow in the game given just how little screen time she has), but after reading it, she quickly became one of my favorite characters. I'm including Ghost Academy in here instead of in the comics section because it's directly connected to these novels, and they reference back and forth to each other. All great and worth reading, and they will give you a new appreciation for Nova if you found her lacking in SC2.
Dark Templar Saga - Firstborn, Shadow Hunters, and Twilight
READ THEM NOW! These are some of the best novels I have ever read. I would recommend them not only to StarCraft fans, or even to sci-fi/fantasy fans, but to any book lovers. I mention this trilogy in the same breath as classics such as Foundation, Narnia, and Lord of the Rings. From start to finish, they are amazing, and they also are the best books for understanding the gaps between StarCraft and StarCraft II. Plus, you get to tell people that you read the good Twilight.
Heaven's Devils Duology - Heaven's Devils and Devils' Due
Heaven's Devils was a real chore to read through... It was far from the worst book I've ever read, but it wasn't particularly good. I will give Deitz credit- the man knows how to write great action sequences. But he has no clue how to link them together with a solid and engaging plot. Devils' Due was much better in that regard- there wasn't nearly as much action, but it kept things interesting regardless. I won't go into spoilers, but I will say I cried when Raynor was hearing his father's last words; if nothing else Heaven's Devils is worth reading just so Devils' Due makes sense, and the latter really is a great book.
Comics - StarCraft (Wildstorm comics) and Frontline
I'll refer to the Wildstorm comics as the "War Pigs Saga" for simplicity. I have issue 0 which comes with the Wings of Liberty Collector's Edition, you're not really missing much if you don't have it... Then again, the entire series is pretty dry and mediocre. You learn about the Warpigs, and why they're already working for the Raiders... There's really not much beyond that, I wouldn't recommend it. Frontline is very much a mixed bag... Which is to be expected considering that there's so many different writers involved. All in all, I'd say it's worth a read, as some of the side stories really are interesting, and explore parts of the StarCraft universe which simply don't warrant a full novel's attention.
Others - Shadow of the Xel'Naga, Speed of Darkness, I, Mengsk, and Flashpoint
There's no clean way to organize these, so I'll just clump them together here at the end. Shadow of the Xel'Naga is not only the worst StarCraft novel I read, it's one of the worst novels I have read in my entire life- certainly the worst that I've actually finished. It felt like so many moments were just shoehorned in to show different units from the game, and nothing of consequence really happens in the book. The book was unable to focus on any real plot, just jumping between scenes at random like an ADHD kid who just washed down a piece of sugar-coated crack with a mouthful of espresso. No one important is effected in any manner whatsoever: Anyone who was there from the games left completely unchanged, and anyone knew either ends up dead or is never heard from again; and rightly so! This book does not deserve to be remembered, avoid it at all cost. That rant aside, let's get back to the other books...
Speed of Darkness is decent; it's interesting, and gives a neat look into the horrors of resocialization, but the overall plot is rather dry. Not a bad book, but not a great one; I'd recommend reading it if you get the Archives, though I wouldn't go out of my way for it.
I, Mengsk is one of my favorites. Then again, you can probably tell by my choice of avatar that I'm a fan of Valerian, so I'm probably biased, but it does give a good bit of detail for the backstory of both Arcturus and Valerian, and showing how different they truly are from one another.
And finally, we have Flashpoint, which connects Wings of Liberty to Heart of the Swarm... If that was all it did, I'd say it's not really that important, as there's not that much that needs explaining that doesn't get explained in HotS itself. However, it does a great job of this, and it also has something else going for it: It goes into depth about the relationship that Raynor and Kerrigan had during the first episode of StarCraft, no longer leaving us to try and imagine and fill in the gaps between "Yeah, but you were thinking it." and "Drop the knight in shining armor routine; it suits you sometimes, just not- not now.", with those two lines implying that there was a pretty big gap we weren't seeing in their relationship. All in all, an excellent book, with lots of development for Raynor, Matt, Kerrigan, Valerian, and even a good bit for Mira Han.