bogusheadbox, where are you located? If there is a GW shop near you, go there and have a game demo run for you. They will show you how it works, how the "phases" in each turn works, etc. Then grab a rule book and tell them you want to figure out for yourself the target numbers for your dice rolls. You'll have most of the game mechanics sorted once you have that understood. Like any GW employee, I would recommend the Assault of Black Reach box set simply because it contains both Space Marines and Orcs, one squad of mooks, one heavy-hitter, and one leader-guy. So basically, once built and primed and basecoated, you can play with either Space Marines or Orcs in the store, or versus a friend. Good way to get started. However, note that the rulebook in that box set is now out-of-date; the new rulebook has got new rules goodies in them, so far I like what I've seen.
MadDog, I've read the first book of the Horus Heresy as well, quite interested in it since it seems like everything started from here. I got book two, but it wasn't as gripping as book one. The audiobooks make for nice background while I'm "working" on the minis.
kome, thanks for pointing out the Tau. I was considering them, but holding off till I know more. I just might build an Ork army, they seem like fun if nothing but blind assaults into the enemy line and simple dice-whoring! And I can practice my painting on them too since I can "not take them too seriously." Imperial troops are too... meh for me. I like my fancy armor and fancy gear (hence Space Marines and Tau).
FrenchToast, thanks for speaking up. Maybe we can compare painting notes? I've always struggled with my painting. The GW shop guys always say it's very easy to do, and yes, it is if you just want "playable quality" paint jobs but I'm aiming for the best I can do --- I'm not stupid enough to compete in the Golden Demon, but can you blame me for wanting to paint to THAT standard? I like the minis I see in the pictures in the books, and I want my minis to look like those.