Ditto the gray selection. I love a gray cape cod . . . and depending on the brick you can do light/dark etc. and some trend towards blue and others don't - lots of flexibility there. White trim and black shutters and charcoal gray roof (we have Moire Black and it is a great charcoal - not too dark or too light and goes with everything). I think a red brick foundation with buff mortar is the most classic look you can find - and unlike SpringtimeHomes - I think it is beautiful - much better than ugly brown brick ;). I am a classicist though and Springtime is not - we absolutely do not share the same aesthetic. I would guess with a cape cod you and I have a similar aesthetic . . .

Cream to match the siding would be safe. With your color scheme just about any color would work. Drive around and take note of what others have done and see what grabs you. And remember, you don't have to paint the foundation at all.

What do you mean by stained? Zinsser makes a waterproofing paint that is good for painting concrete block.

Since you have brick in the front, I would try to match the siding color. But you can't see it from the street so you could just leave it white.