Spain Itinerary for the end of May and beginning of June

Go straight to Seville from Madrid on the train.
Seville 3 nights
(You could take a day trip from Seville to a coastal town like Cadiz or some other. I went there last New Years Day on a full day trip with a bottle of Rioja wine watching the sunset over the Atlantic).
Bus to Ronda
Ronda 2 nights
Bus to Cordoba
Cordoba 2 nights
Train to Madrid
Madrid 1 night

Are you flying in from the US or Canada? I've never heard of a 4:30 AM arrival time. If that was a typo and you are traveling across the Atlantic, you should consider the possibility that you will feel dreadful upon arrival from a combination of jetlag and sleep-deprivation. I totally write off my arrival day. I try to stay outdoors and walk around to help my body clock reset to European time, but I am in a mental fog and would not try to do any real sightseeing that day. Some people are not as badly affected as I am, of course, and there are those rare birds who actually get a good bit of sleep on the flight over. But for me, yours would count as a 7-day trip.

Although it has other attractions, Madrid's #1 claim to fame is its art museums. Given your interests, it wouldn't be unreasonable for you to spend all your time--except the last night before your flight home--elsewhere in Spain. One good use of part of the very iffy arrival day is taking a train (or bus) to one of your other destinations. That will be one travel leg you don't need to do on Day 2 or Day 3, when you can put the time saved to more productive use.

It may be quite hot in Andalucía in late May / early June, but if you're up to it, you could head to Cordoba on your arrival day. Before progressing too far with that idea, you really need to look at the weather situation. For a quick look, check the colorful weather-summary chart on Wikipedia. I've linked to Seville's entry. The numbers are pretty frightening. Actual day-by-day stats are more useful as far as I'm concerned, and they're available from timeanddate.com. I've linked to Seville's June 2018 weather, which wasn't bad at all at the beginning of the month. Be sure to check several more years to get a more comprehensive picture.

If you decide your timing isn't great for Andalucía, you could split your time between Madrid and its excellent side-trips (Toledo, Segovia, etc.) and Barcelona. It's a big country and there are many other possibilities.

It's really difficult to guess how long it will take to get out of the airport and onto an inter-city train--and of course your flight could also be late. So it's not usually recommended to buy Day 1 train tickets in advance, even though doing so usually saves money. But Cordoba is not terribly far from Madrid, so a last-minute train ticket bought that day will not be horribly expensive.

The other two major cities in Andalucía are Seville and Granada. You could just about squeeze in the those two, along with Cordoba, in the time you have, if you are prepared to ignore Madrid. Complicating the decision is the likelihood that you may find the Alhambra tickets difficult to obtain. I wouldn't try to include Granada if I couldn't get Alhambra tickets.

If you want Ronda, that is going to be a very difficult squeeze. Either Cordoba or Granada might have to go. Although there is public transportation to Ronda, some folks would rent a car for that bit of the trip, treating it as a day-trip from Seville.

Note that none of the places I've mentioned except Barcelona is on the coast, so if time on the water is a must, you'll need to skip at least one of the more (traditionally) important Andalucian destinations to fit in time on the coast.

Having just returned from Spain, I would highly recommend Sevilla. I went to Cadiz as a day trip from Sevilla and I was not really impressed with either the beach or town.

Margaret

Thank you for the replies! The insights and suggetions are valuable. Yes, acraven, you're right. I looked at my iphone calendar for the arrival time and didn't realize it stores the time where I live. We arrive in Madrid at 11:30 am. Taking a train south would be a good way to catch up on sleep. As of now, I don't think taking the time to go to Granada to visit the Alhambra is worth it. Unless several people think it's that magnificiant to do so.

I don't think taking the time to go to Granada to visit the Alhambra is worth it.

I would keep Ronda and save the Alhambra for another trip, given what you will see in Seville and Cordoba. The whole month of May (the general admission tickets) are already showing as sold out. So you can see that it has big reputation

So we have 8 full days

Sorry, no you don't have 8 full days, so stop telling yourself you do. You have 7.

The day you arrive at noon-ish on a redeye after flying half-way around the world is not a usable day (you will be too wiped out to accomplish much beyond trying to stay awake until it gets dark, which you should). The best way to salvage something useful from that day is to push on to your actual destination (as long as that doesn't involved you driving - riding a train or bus is OK, you can't seriously hurt anyone that way). It's best to resist the temptation (which will be very strong) to sleep on a train that afternoon; if you do succumb, it'll just delay the adjustment to local time another day -- and you do not have enough days to lose any to that. Try to stay awake until after dark on your arrival day (not easy but quite important), then crash a sleep deeply, wake up the next morning feeling almost human and more-or-less on local time.

So, 7 days to use on the ground. You will want to limit your stops to just 2 or 3 locations.

Is this 2019? Looks like some big sports game in Madrid during part of this time with super inflated lodging prices. That might impact plans, but hopefully by June 5th pricing is back to normal.