First Visit to Spain

I highly recommend San Sebastian for its setting and there is some serious cooking going on there you can smell it often walking the street it made my my stomach growl. If you like modern art and architecture I would take a daytrip by bus or car from San Sebastian to Bilbao and visit the Guggenheim Museum, (although to me the outside is more striking than what is inside).

You should pinpoint and set your itinerary on going to those places that offer the what that has prompted your interests in going to Spain. If you have not already you should get some kind of guide book. But of course I think most would like Barcelona more than Madrid though it is a good base for day trips to Segovia and Toledo. It depends on a person's interests.

Andalusia (e.g. the cities Seville, Cordoba, and Granada) I hope to do that maybe two months from now

I know people get tired of seeing this recommendation ---- BUT ----- go to your public library and find all the Spain related DVDs, travelogues, guidebooks, etc. Review them and see what appeals to you. Spain is a big country with a lot of contrast that make three weeks seem inadequate. The bus system in Spain is excellent and there is no place that public transit does not cover. If you are not big into planning consider one of R Steves' Spanish tours.

Our first trip to Spain was in October 2017 - 14 days, not counting arrival/departure days. We flew into Madrid and out of Barcelona. I had wanted to visit the Rioja wine country, but just couldn't make it work. We ended up taking a day trip out of Barcelona to the Priorat wine country - which was amazing!

Day 1 - Arrive Madrid (Hotel Artrip)
Day 2 -Day trip to Segovia/Pedraza
Day 3 - Prado, Thyssen-Bornemisza
Day 4 - Royal Palace, Reina Sofia
Day 5 -Naval Museum, Retiro Park
Day 6 - Train to Seville; Cathedral (Hotel Becquer)
Day 7 - Alcazar
Day 8 - Day Trip to Jerez de la Frontera and Cadiz
Day 9 - Indian Archives, Triana District
Day 10 - Train to Barcelona (U232 Hotel)
Day 11 - Park Guell; Maritime Museum; concert at Palau de la Musica Catalan
Day 12 - Sagrada Familia; St. Pau
Day 13 - Day trip to Priorat Wine Country
Day 14 - Day trip to Tarragona and Sitges
Day 15 - Day trip to Costa Brava and Girona
Day 16 - Fly home

We obviously didn't see everything Spain has to offer, but we had a great time.

We took cabs back to our hotels a few times, but generally we walked everywhere - except to Park Guell from our hotel in Barcelona.

The places mentioned in this thread so far (excluding Traylaparks' post) are the ones people seem to try to get to first. The issue with trying to do them all within 2-1/2 or 3 weeks (please do make it 3 weeks), aside from geography, is that most of those places have really wonderful side-trips you can make that don't require you to travel half-way across the country to reach the next destination. So you do need a guide book, and you need to decide whether you want to try to cram all those places into the time you have, or whether you'd rather not cover quite that much territory and have a more comprehensive look at the cities you do visit. Keep in mind that time spent on trains/buses/planes is not sightseeing time.

You can check the travel time between most of the mentioned destinations on the easy-to-use Deutsche Bahn website. It will not give you fares.

There's a significant difference between the weather in Andalucía and in the Basque Country, so that might be a consideration. In Andalucía you have the risk of highs well into the 80s F (so I'd push it toward the end of the trip, if possible); in the Basque Country it will be cooler (likely not cold) and might be quite rainy. Rain is common there even in mid-summer. So if including the Basque Country, I'd try to head there early in the trip.

The extent to which you'll need a car will depend on whether you want to get to hard-to-reach smaller places, such as the white villages in Andalucía. There are extremely fast trains connecting Barcelona-Madrid-Cordaba-Seville. Driving along that axis would be much slower.

San Sebastian-Bilbao has frequent and reliable bus service; the train between those two cities is scenic but much slower.

Edited to add: I see that in your original post you mentioned only Madrid and places north thereof. That would be a fine idea for the time you have available. I spent 89 days in Spain in 2016 and barely got south of Madrid; I decided to leave Andalucía for a later trip.

I’ve frequently told friends that if you’re only going to visit Spain once, you should see Madrid, Segovia, Toledo, Sevilla, Córdoba, and Granada. Unfortunately, that’s a lot of area to cover in 3 weeks. I spent 18 days last year in northern Spain (Galicia, Asturias, Cantabria, Navarre, and Basque area) alone. On another visit it was 3 weeks in Andalucia and Murcia by themselves.

With 3 weeks, including San Sebastián & Bilbao.

Day
1. ARRIVE Barcelona (5N)
2. Barcelona
3. Barcelona
4. Barcelona
5. Barcelona
6. Fly to San Sebastián (3N)
7. San Sebastián
8. Day to Hondarribia
9. Bus to Bilbao (2N)
10. Bilbao
11. Fly (via Madrid) to Granada (2N)
12. Visit the Alhambra
13. Train to Seville (4N)
14. Seville
15. Day to Cordoba for the Mezquita
16. Seville
17. Train to Madrid (5N)
18. Madrid
19. Day to Toledo
20. Madrid
21. Day to Segovia
22. DEPART Madrid

In January I had a long conversation with another tourist (we were in Vietnam) who happened to be from Bilbao. Since that part of Spain has been on my list for a while, I quizzed him. He the best time of year was September-October. He said that outside of Bilbao and San Sebastian, a car was the best way to go.

For me, Madrid would only be a must-see if you want to spend a couple of days in museums enjoying some of the best European artists' paintings in the world.

I will warn you about one thing. Spain is as addictive as Italy. I planned a trip to Spain because I'd had a desire for over 20 years to see the Alhambra. I planned a full 21 days in Andalucia, plus a couple in Madrid (I am an art lover) so that I'd see it "in-depth" and cross it off my list. Over the next 3 years, I made two trips back which included Barcelona and surroundings, both of 3 weeks. Now I'm seriously thinking about Galicia and the Basque area this fall. After all, it's been 2 full years since I was last in Spain.

Whether or not you have any interest in a tour, I would suggest you look over the itineraries of the Rick Steves tours in Spain, especially “Best of Spain”, and also the “Basque” Tour. They will give you what Rick Steves and his many guides think are the most enjoyable stops in Spain. It would be difficult for you to duplicate the itinerary in the same timeframe on your own, especially without a rental car. The tours generally have dedicated buses and drivers that know precisely where they are headed. Also, on your own, you would likely want to spend more time in Barcelona and in Andalucia than the tour does, and many tour participants do that on their own before and after the tour. But these itineraries are great inputs to your own planning.

I like a physical map of Spain, easy to order on Amazon. Michelin map is great. We have been in Spain four times and yet to see all. Three weeks yes a must. Pick an area and concentrate on that region. We did Andalusia Region last year and we enjoyed Sevilla,Granada, Córdoba, Cadiz and side trip to Tangier, we also toured Jerez and Rhonda, Frigiliana, and finished in Malaga. I have planned trips based on this forum, so enjoy the many traveler's thoughts for you.
Safe travels!