You could go the MI2 route and do hand-drawn/sketched backgrounds. Or you could got the SMI route and make the backgrounds with Deluxe Paint II
. It's free now since it's an ancient DOS tool. But it's what was used to create all of LucasArts adventure graphics up until SMI/Indy3/Loom (actually now that I think of it, I believe FOA used it as well). It has the ability to do either clean, uniform noise, or random noise gradient fills (you can see this in LucasArts' games). It's a great program. I once tried to VGA-ify a Space Quest II screen with it. Not very good at it, but it would've been interesting to see an SQ2 screen VGA-ified much like how Loom, Indy 3, and SMI were VGA-ified LucasArts style. Here's a cool tutorial
as well for how to get a classic LucasArts look.
It also supports rotating palettes (that cool gradient animation effect on things like the lava underneath the honkey head in SMI. AGS supports rotating palettes, incidentally, but only in 8-bit 256 color mode. Incidentally, LucasFan also used Dpaint to VGA-ify the graphics for Maniac Mansion Deluxe.
Nice screen, Scapetti! A collage-type remake of other MI graphics is a neat way to go as well. After all, it's what the King's Quest I and II AGS remakes did for their first versions (they've since been re-released with brand new hand-painted backgrounds).