Recommendations for a month-long driving trip to southern/central Spain and Portugal

Here are a few initial thoughts on your plan:

Time/Distance - I think you will find that one month is not nearly enough to visit all that you want to, just tallying it up you'll probably more around 50-70 days. Don't underestimate distances too, you'll probably spend 1/4 of your vacation time just driving, Portugal and Spain are not so easy to combine as one would think.

Car - Having a car is good for shorter trips of a week or two focusing mainly in the countryside and not big cities. You have only listed big cities on your wish list, so I do not see any advantage to hiring a car, you'll find parking and navigating the big cities a nightmare with a car. Gasoline is significantly more expense in Spain than in the states, currently in Spain average for US gallon of gas is $6.87.

Weather - Late June into July are some of the hottest days in Spain, in the south it will average around 100 degrees F. Not a good time to visit the area. You will have to cut sightseeing time in half in order to accommodate for the high temps in the mid day.

I think you need to seriously reconsider the feasibility of your current plan so it does not become The Amazing Race.

My recommendation is to instead head north from Barcelona and do a roadtrip in Northern Spain before swing back down to Madrid. Northern Spain aka "Green Spain" is quite the contrast compared to the south of the country, and looks more like Ireland mixed in with the Alps. The weather is much more temperate. From medieval villages, to the picturesque wine regions, the emerald waters of Bay of Biscay, the culinary delights of the Basque country, the Celtic culture of Galicia, and finally the towering jagged peaks of the Picos de Europa.

Here are few more reasons why you should consider the north of Spain: https://theculturetrip.com/europe/spain/articles/15-reasons-to-visit-green-spain-at-least-once-in-your-lifetime/

For where you want to travel, there isn’t enough space to write all the places I’d find interesting. Where you stop and what you see is dependent on your likes. Large/medium/small towns, castles, hermitages/convents/monasteries, outdoor activities, beach/inland, etc. If this is your first trip to the areas you want to visit, then you’ll want to see the popular tourist sights. One could spend a third of your month, or more, in just Granada, Córdoba, Sevilla, Cádiz, Lisbon, and Porto. A few medium sized cities we enjoyed are Santiago de Compostela, Zamora, León, and Burgos. A nice smaller town is Lugo and its Roman wall. There are many more.

For hotels in Spain, my wife and I like staying in Paradors if there’s one in the town we’re in. If not we just look for hotels with character, charm, and parking. There is no shortage of them in the country. We don’t generally begin looking for lodging until we have a route and basic itinerary laid out.

A month is too tight to go all the way to Porto and loop back towards Madrid, but I think it works out if you turn east from Lisbon towards Extremadura.
Here is what I come up with off the top of my head, I do not claim that this is the best possible route but it fits in a month (barely- I have 31 nights). It is fast-paced and it would exhaust me, but some people do not mind long road trips.

• Barcelona: 2
• take train to Valencia: 2
• Elche or Murcia: 1 (I do not care for Alicante)
• Cabo de Gata: 2
• Granada: 2
• Córdoba: 2
• Sevilla: 3
• Arcos de la Frontera: 4 (use as base to tour the entire region between Cádiz and Ronda)
• Tavira: 3
• Lisbon: 4
• Evora: 1
• Trujillo: 2
• Madrid: 3

To be honest, besides Valencia, highlights are a bit scarce on the coast between Barcelona and Andalucía. There are a few noteworthy places: Tarragona for Roman ruins, Peñíscola, pretty coastlines around Denia... But it's not much.
You would save a lot of time landing in Madrid and heading straight to Córdoba by train to start the road trip there (then go Cordoba, Granada, Arcos, Sevilla).
Also: the heat is 🔥 at that time of the year in the south of Spain. I went there often in August (mom was a school teacher), and 40C was usual in inland areas. It is probably worse nowadays.
It does not prevent a visit, but it gets annoying.

I agree that mid-June to mid-July is an ideal time to be in northern Spain near the coast. That's the area I headed to in 2016, to cool off after visiting Extremadura. There are many interesting towns and cities in the north, and the scenery is nice--especally in the Basque County, the Picos de Europa and Galicia. A few years later, having observed the huge number of 100F summer days down in Andalucia on my favorite weather website, timeanddate.com, I planned my month in Andalucia to begin on April 10. That also worked very well.

Mid-summer travel through a string of small southern villages might work when traveling by (air-conditioned) car, but day-long sightseeing in cities, when you wouldn't be cooling off in the car frequently, would mean a less-than-ideal experience. Believe me, I know; I went to Sicily and Puglia during the summer of 2015. Andalucia is hotter than southern Italy.

There are some very nice villages in the mountains of Extremadura and Castilla y León which would not be too out of the way enroute from Lisbon to Madrid, including Robledillo de Gata, La Alberca, San Martín del Castañar, Miranda del Castañar, and Mogarraz.

If you go north to Porto, depending on your route to Madrid the Ribeira Sacra/Cañón de Sil area is a stop.

For driving in Portugal, you may need a toll transponder if you are going to drive a car registered in Spain on the "A" or toll roads. You can buy them in advance, or your rental agency may provide them.

A month in a car driving takes me back to 1990 when my wife and I did the same in Italy/Austria/Germany............. I ask a question based upon experience..........."When was the last time you spent a month, 24/7, with your wife (in a car)?".
Keep in mind everything melts in the heat of Spain while stored in a car (even air conditioned and especially when you get out to explore a village and the vehicle is left in the heat).
Take out a map of Spain and strive to comprehend the expanse you are considering driving and the time it will take to do so. Add in a flat tire...........stress of parking and safety...........time each person will dedicate to being focused upon safely driving without being fully engaged in experiencing the journey. Spain is our favorite destination and we have driven within the country, but............. driving is our last option as the bus and train service is a wonderful option and the expense of going long distances is manageable due to a competitive value airline industry. By the way, no matter how you travel, for a journey of this duration please avoid being luggage mules (kiss of death to enjoyment). Start with fewer clothes and enjoy some shopping during the trip (clothes become wonderful memories and souvenirs).
Consider setting aside a mentality of SEEING destinations and crafting the time to BEING in destinations in order to EXPERIENCE the journey as this mentality creates far more wonderful MEMORIES for us.
https://www.viamichelin.com
The via Michelin link will help you comprehend the task you currently have defined for car travel. My hope is you will use it to understand the geography can be best explored via other transport.
My best guidance to you both...............For a 30 day journey make it clear taking time to explore on your own is "OKAY" and take advantage of having some "me time". It was on day 10 my wife and I realized we were "enjoying" too much time together.