Spain--8 Days

For Madrid, it's hard to beat the Hotel Europa on Puerta del Sol. It's a nice hotel in a great, central location. For the first day, you can start walking from Puerta del Sol towards Plaza Mayor and on to the Royal Palace. Spend a couple of hours there and then head to Mercado San Miguel for some tapas/lunch. After that, go to Retiro Park and wander around.

Day 1 - Arrive Madrid - 3 nights
Day 2 - Toledo day trip
Day 3 - More Madrid or Segovia
Day 4 - Train to Granada - 2 nights
Day 5 - Alhambra
Day 6 - Train via Córdoba (for Mezquita) to Sevilla - 3 nights
Day 7 - Sevilla
Day 8 - More Sevilla or Jerez
Day 9 - Depart Sevilla

Thank you both for the advice! Is it easy to catch trains while we're in Andalucia, or should I try to book them in advance? Also, are restaurants easy to get into without reservations, or do they require them? Or, should we simply eat our way through Spain with tapas places?

You may be too tired on arrival (assuming you're flying transatlantic) to tackle something like the Royal Palace. I wouldn't pay for that in advance, since you may prefer just walking around and enjoying the sights. Rick has a good walking tour of the area around the Plaza Mayor and the San Miguel Market. Another possibility to keep you moving and outdoors is Retiro Park. It's large and free. Not far away (also near Atocha Station) is the Botanical Garden. There is a fee to enter; I enjoyed it on my first day.

The Spanish eat meals extraordinarily late. Lunch can be from 2 to 4 PM. Locals wouldn't normally eat dinner before 10 PM, though you'll find places targeting tourists that serve earlier. Being unwilling to eat dinner so late, I depended very heavily on tapas, especially for my evening meal. Anytime I was near San Miguel Market, that's where I went.

I'm sure a reservation would be smart for any special place you want to go for a sit-down meal, especially at dinnertime.

Stephen's idea is just what I would suggest, too. I go to Madrid every year or so (last May, going again this May). By the time you get out of the airport and into town, it will probably be late morning (10:30-11:00). You could check in to your hotel (or just leave your bags if your room is not ready) and head out. You will want to stay outside as much as you can and keep moving. The Royal Palace, Plaza Mayor, Puerta del Sol, and Mercado de San Miguel are all within blocks of each other, easy walking. Retiro Park is beautiful, and can take as little or as much time as you want to give it. To give you an idea, last May I got into the area around 11:00. I checked in, showered, then walked down to Sol, met up with friends to walk through the Plaza Mayor, then had lunch at Mercado de San Miguel. Then we took the metro to Templo de Debod. By the time we walked around Plaza de Espana and got back to Sol, it was about 5:00. We all opted for an early (by Spanish standards) dinner, then went our separate ways for the night because that was about all of the energy we all had after arriving on overnight flights.

Is it easy to catch trains while we're in Andalucia, or should I try to book them in advance?

You may book your train in tickets in advance (up to 90 days) at considerable savings on the Renfe website.

Here is a helpful website on how to order Renfe train tickets online.

The man in seat 61 is also a very informative website.

BTW, I like David's itinerary.

Since you plan to fly out of Sevilla, then visiting Madrid at the start of your trip makes sense. However, if you opt to depart from Madrid, then I'd suggest traveling to Córdoba (upon arrival) for an overnight, then taking the bus or train to Granada from there, and ending your trip in Madrid. Córdoba is a nice quiet city to get over jet-lag, IMHO.

In terms of eating at restaurants...

Since I was traveling with my elderly mother who eats a very early dinner, we mostly ate tapas in all the cities we visited.

In Córdoba, our favorite meals were at "Casa Pepe de la Judería", and at, "Bodegas Mezquita".

In Sevilla, "La Antigua Bodeguita", on Plaza San Salvador became our favorite place for authentic tapas. The food was delicious and we ate there three days in a row!

In terms of hotels...
We stayed at Hesperia Córdoba in Córdoba; Hotel Amadeus and Hotel Fernando III, in Sevilla, and Hotel Anacapri in Granada.

Have a wonderful trip!

Edit to add...

Make sure to book your Alhambra tickets 3 months in advance.

Keep in mind that the weather in Andalucía will still be hot in September.

With my itinerary above, look at a very early start on Day 6 ...
Train via Córdoba (for Mezquita) to Sevilla - 3 nights
On the current schedule you have ...
TRN13062
Dep 06:45 GRANADA (Spain)
Arr 08:13 ANTEQUERA-SANTA ANA (Spain)
AVE 2083
Dep 08:23 ANTEQUERA-SANTA ANA (Spain)
Arr 08:54 CORDOBA-CENTRAL (Spain)
Store your luggage in Cordoba for the day, to visit the Mezquita and other sights.
http://www.cordoba24.info/english/html/consignas_ferroviarias.html
Then continue on the further 45 mins by train to Sevilla in the late afternoon/ early evening.