I love the Andalusia area! I studied in Sevilla one summer, and it's gorgeous. From there, it's easy to do trips to Granada, Cordoba, and even Gibraltar if that interests you.
Barcelona has a lot to see around the area. When I was there in the past I drove up to France for the day and enjoyed the curvy coast so I'm not much help there.
In Madrid. I went to El Escorial, it was the residence of the King of Spain and is very cool to walk around and be in a castle. It's also not very far from Madrid via train. I also went to Avila. The old town is surrounded by medieval walls. In both Avila and El Escorial we forgot time and arrived right at siesta. Both cities shut-down. In Avila it reminded us of a zombie movie. Nobody was around. In El Escorial the castle was still open to tour. Keep that in mind if you travel to the smaller cities. Unlike the larger Madrid and Barcelona that have a lot still open during siesta.
Remind me again what time of year you are going? I am thinking it is June, which could make Southern Spain a terrible option because it gets so hot. What about going to San Sebastián for those extra few days? The food there is supposed to be phenomenal.
San Sebastian is wonderful, and the food there is definitely worth a trip. But, I'm not sure how easy it is to get to/from Barcelona.
Is there a particular reason you're going to Valencia? I would be more inclined to spend days 10-14 going to another region like Andalucía or the north of Spain- San Sebastian and Bilbao and all the lovely towns in between, for example.
Re: Madrid, another nice day trip from there is Segovia.
From Barcelona, I would go to see the Dali museum in Figueres. I went years and years ago, so I can't tell you a thing about the town, but the museum was great. I haven't been, but I hear amazing things about Cadaques. Have you already been to this web site? www.spainthisway.com/regions/catalonia.php