Well a smooth red would probably look good,Mabey like this
Well to make a new class you need to find the styles folder and look for something named style.css, open it go to line 283 and all the style for the header well be there.I am not sure though if thats where your style sheet is.I have never used the Genesis theme.