Madrid or Seville?

None of them should be too hot in May.

Since you don't like museums and prefer more "traditional" Spanish feel and food, I'd recommend Sevilla over Madrid. For me, Madrid as a city is nice but not very impressive. But the art museums are top notch, something that won't appeal much to you. However, you might still want a night in Madrid to at least catch the highlights and with 7 nights, you can easily afford it. Then take the AVE 2.5 hours to Sevilla.

Another option to consider is Valencia instead of Sevilla. Also just a 2.5 hour AVE ride from Madrid and the city has wonderful character and food. And if you like modern architecture, the science center complex by Calatrava is impressive. Valencia is also more convenient to Barcelona, just a 3-4 hour train ride up the coast. Tarragona would also make for a good overnight stop on the way. It's a dramatically set city on the coast filled with Roman ruins.

I would recommend flying in and out of Madrid if possible. The flight from Atlanta to Madrid is basically 8 hours...that from Barcelona is much longer with a lay over in NYC..if your miles will let you, the shorter flight is the better of the two. As for which city.....Madrid is a large city, and has some excellent restaurants as well as major tourist sites.

Barcelona is also large, called by many 'the Paris Of Spain" and has a much different vibe than Madrid...still lots and lots of tourist, and some excellent restaurants as well.

Seville...would recommend you take the AVE high speed train...not the plane..2 1/2 hours from the Atocha Station in Madrid to the station in Seville. No airport hassel, etc. You can get tickets about 60 days in advance on the Renfre web site at a substantial savings.

If you have the time, an over night trip to Toledo, from the Atocha station, 1/2 hour will be well worth the effort...and some excellent food there as well.

Excellent guide book The Moon Guide To Spain..get a copy, well worth the money.

You can never know the weather with any certainty. Generally May shouldn't be bad for either Seville or Madrid. Madrid should have warmed up enough to be comfortable and Seville shouldn't be too warm in May.

Suggest you fly directly to seville as it is an easy flight connection via madrid. Stay several days then take AVE train to madrid. Stay couple days in madrid then take AVE train to barcelona. Fly home from barcelona.
I typically abhor recommending a couple of nights per location, but this is a stated travel pattern for you.
Benefit is you will comfortably traverse a great geographic distance, be able to view the countryside going from place to place and experience three different aspects of spain.
Train travel on renfe is quite comfortable and time efficient. Second class tickets are all you will need. Advance purchase saves loads of money. Do internet research to learn the process and rules for ticket purchase.

Because of your frequent flyer restrictions, fly into Madrid, then take the train to Seville if that's what you want see. One caution: I was in Seville in early May 2012, and the temperature every day was over 100 degrees. Perhaps it was a fluke, but it was miserable. I would be tempted to go with the suggestion of Valencia myself.

It's funny. I was in Seville in April 2012 (during April Fair) and it was still chilly from a cold winter. I don't think it ever got over 60. I guess it warmed up in hurry after that. Just shows, you really never know about the weather and averages aren't always good predictors.

We just returned from Spain. We flew into Madrid, drive to Granada, stayed for 3 nights. We then drove to Ronda, which is an exceptional small city. We stayed at Ronda Mountain Resort and really enjoyed it. I definitely recommend it. We then headed to Seville for 2 nights before returning to Madrid for 2 nights. We are foodies so we enjoyed Granada and Seville. Now we did have a few exceptional meals in Madrid but with so many options you have to do your research or ask a few locals.
Madrid is definitely more of a metropolis with great architecture. We did prefer the smaller quaint cities.
Chris

Sarah, with only a couple of trips to Spain I'm hardly a destination expert (going back next Fall). Your trip while a bit short is like a tapas tour. IMO Madrid is best an arrival or departure city; it's not nearly as captivating as Rome, Paris, London, Prague, etc. However, the nearby cities of Toledo, Segovia, Avila and Salamanca are simply unforgettable. I'd land in Madrid, rent a car and visit each of these smaller gems in a multi-day trip.. Barcelona, on the other hand is quite unique and so much to see. Did I mention the splendid sites in nearby Girona or the Dali attractions in Pubol, Figueres and Cadaques? Using Girona as a base A couple of days would suffice.
I'd Save Sevilla and south (Arcos, Ronda and Southern Portugal) for another trip.
Wishing you joyful and safe travels.

If you're not into art, I think Madrid is skippable on this trip. Of the larger Spanish cities, it has the least character in my opinion. Sevilla had absolutely fantastic food (do try La Bulla, La Azotea, La Brunilda and Zelai) which was significantly more affordable than what we had elsewhere in Spain. It's also a beautiful city with lots to offer during the day and at night. Barcelona offers the great architecture you're looking for, including Gaudi, as well as very inventive food. Do try Tapas 24, and if you're a foodie, try to secure a reservation at Tickets. Totally worth it.

I just returned from a trip where I used Madrid as a home base for 5 days, all staying in VRBO and Airbnb apartments (day trip via train to Toledo) and then took the train to Seville (it was less than 50 Euros with advance purchase and a nice experience) for 4 days then returned to Madrid for 2 nights before a flight home to Chicago. Once you are in Spain, the trains are SO easy to use that I'd pick that vs. navigating an airport. Keep in mind that the Madrid airport is HUGE and takes hours to navigate point to point at least if you are dealing with the international terminal, and it is also a 30 euro taxi ride from the city (or you could try to deal with the airport metro but I'd guess it is a pretty long ride). The Atocha train station for the high speed trains is super easy to access from any part of Madrid. I don't have experience with Barcelona, but my friend is a super seasoned traveler who was there before meeting me in Madrid. Her comment was that it was nice, but that it could be almost anywhere that has a nice beach. If you want a real Spain experience, my vote would be some time in Madrid, some day trips to Segovia or Toledo from there, and then Seville for sure. Don't miss Seville.

Your itinerary makes sense, except I'd train from Madrid to Seville (AVE train is probably cheaper and definitely faster once you figure in transit times, etc. About 2.5 hours city center to city center). I enjoy Madrid for the art and big city feel, but would definitely choose Seville over it, hands down. Seville is atmospheric, stereotypically Spanish, and just a joy to be in. I love Granada at least as much, I might even prefer it, but I don't want to add more to your itinerary.

Fly into Madrid, stay a day or two. A side trip to Toledo, overnight, would be wonderful, probably more to your liking than another day in Madrid. Then train to Seville, stay up late, eat tapas, go to a flamenco show (I love Casa de la Memoria). I would make sure to have at least three nights, two full days, in Seville. Fly to Barcelona for a few days (I haven't been in forever, so I can't advise in detail, but it's definitely worth at least a couple days).

OR you could skip Barcelona, do Madrid/Toledo/Seville (and maybe somewhere else in southern Spain like Ronda, Granada, etc) then return to Madrid for your flight home. Barcelona is wonderful, but it's kind of its own world, maybe a separate trip.

Early May will be warm, but unlikley to be completely unreasonably hot. Of course, I just had 90 plus in Seville in late October, so you never know. But with the siesta in the hottest part of the day it won't be as bad as you think. Just be inside or at a cafe from 2-5.

Seville is a must!! I was there in July! And oh my it was hot! However it's always been like that in Seville so the buildings are built tall and close to provide optimal shade! We had an amazing time in Seville! Also I felt like in Seville I got a taste of the real Spain! It wasn't filled with tourist traps like Madrid and Barcelona! The food was amazingly authentic and much cheaper that the other two cities! I can't wait to revisit Seville! Between Madrid and Barcelona I would pick Barcelona! Just watch out for the restaurants on the Main Street that are mostly tourist traps and not good at all! Have an amazing time in Spain!

Flying to Barcelona will eat up the better part of a day, so I'd eliminate it. From the airport head to Toledo, Seville, Cordoba and/or Jerez. These are all beautiful places that will make you fall in love with Spain. They are well connected by fast trains. You may want to end in Toledo since it's the closest to the Madrid airport. You can see a performance of the Spanish horses in Jerez at the Royal Equestrian School (only a couple of times a week, though) or an evening performance in Cordoba. Take in a flamenco show or two. Tour a bodega (winery) or two in Jerez and taste the sherry.