As for some of the restrictions, I was browsing a few other pieces at PJ and they didn't seem to always have the 1 global background colour + 3 extra colours per 8x8 pixel (4x8 widepixel) character (tile) rule going on, but I'll see what I can do.
Well I guess that depends which mode they were done in. C64 has 2 main graphics modes, singlecolor (also called hires) and multicolor.
Both these modes are possible in bitmap and character mode, for images like we do here bitmap mode is what you want.
In the case of multicolor you get 1 background colour for the whole thing and 3 per 8x8 (4x8 widepixels) char.
In hires you get 2 colours per char and the full 8x8 resolution. Basically less colours, more pixels.
Then there are tons of hack modes which people invented through using coding tricks, like flickering between 2 offset mcol images and so on. There are some pictures from Jailbird on PJ I think which are interlaced but he has them on PJ in full 320x200 singlepixel glory. The things is that they do not look like that at all on the real thing, they are just pixelled that way and then when they are compiled they get seperated into 2 seperate mcol images which are then flickered on top of each other, one of them being 1 pixel offset.
So in regards to all of that, I would suggest you to use standard Multicolor Bitmap, 1 background colour + 3 per char. This is a very nice mode to hone your general pixel skills.