Eh, poked around the website you linked. They don't mention their working (print) resolution anywhere. It's a small vanity press, using spot color, so who knows. Anything between 96 dpi and 1200 dpi is possible.
They offer 9 standard colors, black and 8 bold hues, all of which are darker than the chipboard background. They are really just set up for line work, and simple flat colors (clip art and whatnot). That's not to say you can't do pixel art, I think you have some hurdles here.
I agree with Ryumaru that the small figure looks great. The giant is still a problem.
Your source is large, and gray scale that uses subtle shading to convey form and texture. Old school video game sprites are generally much smaller, have limited colors, but almost always a value range. The tools you have are high resolution, very limited colors, no attempt at value range at all. none of these really fit together well.
If the printer is running at even 200 dpi, you could fit your entire original sketch (1000 pixels) on the cover.
If you still want an old-school video game feel, eh... maybe try zx spectrum style. That is, find out what the effective print resolution is. Build your giant from blocks, where each block is N by N pixels, no more than 2 colors per block. And stick with solid blocks or simple checkerboard dithering. It won't be exactly old school but it might be close enough.
Hope this helps,
Tourist