A game set during the Horus Heresy period would be cool. Since at the time the Imperium is at its peak, and you could have more elaborate weapons and explain it as one of the many technologies lost in the intervening 10K years.
I would think that the Warhammer cannon would lend itself extremely well to a squad based game a la Gears of War. The first three books, with some minor edits to make it more suitable for a video game, would make for a great game I would think. Then later the attack on Calth would probably be a great source for a game even if it would be yet one more Ultramarines game, and the Blood Angels getting ambushed could be good, finally the Battle of Terra. Even though Black Library is still milking the Horus Heresy book series, it'd take probably 1-2 years, minimum to crank out a game like this.
You could also do a stealth action series, sort of like Thief or even Deus Ex, based around the Alpha Legion.
I would have to say though, that I was a bit underwhelmed by Space Marine. Not even getting into finer points of how the plot differed from "official" cannon, just little things were a bit off. Astartes are supposed to be significantly taller than the average human, so when they're barely taller than the Imperial Guard officer, a woman no less (so would likely be shorter than a man), that was just kind of wrong. And the fact that their armor has some kind of shield... I get it was a gameplay enhancer, but they could have at least said how it was some kind of experimental nano-repair system. And at the end when he goes with the Inquisitor to protect the Guard commander is extremely unlikely considering the Guard is supposed to be disposable troops that can just be thrown into a meat grinder if needed. I also got annoyed with the Ork gretchins who could come up behind you and kill you before you even saw what happened.