The month of May is not to far away. So whatever shoes you are going wear with make sure they are well broken in.
Madrid, Segovia, Toledo and El Escorial are places you want to walk around to really enjoy them.
I wear comfortable, well broken in casual shoes, like Timberland or Rockports that I can walk in them all day and my feet will not hurt. They are black, water proofed and I can easy polish them when I get they get dirty.
I found in Madrid since I was going out more to tapas bars and resturants, I worn a nice shirt and dark pants. I can honestly say I was more comfortable dressing this way because I could fit in and not look like a tourist.
Have fun in Spain! I certain did and will in the future.
Bill