Thanks for the replies.
@ptoing: I indeed have started to do a layout of the background. It looks like I will be creating tiles that are 8x16 because of the wide pixels. I noticed that on the CPC version of Renegade it flicks 5 creens, and on Target Renegade it flicks 14 screens. They dont flick "whole" screens - just a quater(or something like that). So what your saying is for me to put a grid on the layout that I'm roughing out where the squares are 8x16?
Yes - the background will be that perspective style of the old beat em ups.
@Helm. Yes your right. This has been one of the things that I need to be extremely careful of. There are a few easy on the eye tones on the CPC palette but only 1 grey unfortunately. There is a very easy green that also works well and isn't very harsh. The current picture I posted has 12 colours, so I have another 4 to play with. Looking at the CPC renegade stuff, they do a really nice job of making sure that the characters standout as they seem to keep all the busy areas at the top of the screen, with the ground area a peppered texture of only 2 colours.