Nemesis!
I like them. I made a few scans to illustrate the points.
Nemesis himself is looking fairly on-model, although he's missing that tube that stretches from his head to his back.
I'm not sure if I'd suggest adding it though - it might excessively clutter the design. Something to consider.
I haven't read the entire series, but in your work he seems to be shooting with everything other than his mouth, which is what left an impression with me:
I'll address style since you bring it up. Clearly, the original art style (Kevin O'Neill, I can't speak of the others) is impossible to render completely at the desired size. Not practically, but in principle - because, among other things, it's defined by a high-degree of detail, like this
(1). However, another characteristic is bold lighting & stark contrast, so I suggest going as far in that direction as the limitations will permit.
I know you said you didn't need ideas, but here are some scans of things that might make nice sprites (they're big):
(2),
(3),
(4).
EDIT: I hope my overzealous response didn't kill this thread...
