We loved Segovia and you can drive there very easily from Madrid.
We went to Pedraza de la Sierra, there are several trip reports out there that cover that.
I have never been to San Sebastian and would love that.
Or you could check out the Rioja area.

I noticed the Iberian traveler'd website has some nice itineraries for those areas....
http://iberiantraveler.com/#la%20rioja

Andalucia will be hot in July - Seville around 37 celsius during the day. As an Austalian I don´t consider that unbearably hot and we were in Seville last July and were fine - just stopped frequently for drinks. That said, it wouldn´t be my favourite month to do a lot of sightseeing etc.

As for 50 degrees that someone mentioned - I very much doubt it.

We live nearer Malaga and right now it is quite cool - it has been a very cool April and May and we haven´t even considered going in the pool yet.

If you stayed on the coast in July it would be a bit cooler than Seville.

I love San Sebastian and the Basque Country. I've been to Mallorca, Costa Brava, Madrid etc. but I liked the atmosphere of the Cantabrian Coast and the food above all. Your only problem would be booking a place at this late a date, however I would explore it. No need to limit yourself with Spain since France is next door.

I would do a sampling of Basque region (Bilbao, San Sebastian), continue through the Cantabrian coast, and then go into the Picos de Europa. Weather in July in that area is much more pleasant that in Andalucia.

I would choose somewhere coastal. I would far prefer Andalucia in July to Madrid, as at least you have a sea breeze in many parts. I would have suggested the Costa Brava or Dorada area but as you have already been to Barcelona, that may not suit. Wherever you choose, pick a hotel with ac!
If you liked Mallorca, you could consider Menorca.
On the east coast, I like Peniscola and Tarragona. I also stayed in the tourist resort town of Cambrils which was very nice.