Updating my Europe bucketlist!

I think Madrid is vastly underrated. The Prado is on par with your other major European art museums, and the Reina Sofia and Thyssen-Borzemisa (?) are excellent as well. It has a lovey, lively and walkable city center. It is as different from Barcelona as Sevilla is to Madrid. I felt most cities in Spain had their own personality. It deserves a couple days.

Also, I did Amalfi Coast last year and definitely recommend it. The area is stunningly beautiful. Stay in Naples or Sorrento to see Pompeii and Herculaneum. Paestum is also a good day trip. There is tons to see in this area, and it’s not necessarily easy to string together. It will require some time, but time well spent.

If you do start with London and end with Paris, you are eliminating some choices by default (I don't see going from London to the Cinque Terre and then back to Paris, if you see what I mean). If you did this, I would go to Amsterdam. I get that Paris is magic to many people, and Paris is one of my favorites, but ironically, it grew on me to get there. Florence is also one of my favorites, and actually the vibe I got in Florence reminded me of Amsterdam, or maybe AMS and Paris mixed. If you did go to AMS, I recommend renting a bike. I say this a lot on this forum, and I do it with a grain of salt thrown in, bc if biking is the last thing you would want to do, AMS is not the place to do it. But if you are game, it transforms the experience of the city into something giddy. Just saying. Besides, on a practical level, you can get anywhere in the city in 15 minutes. I would also make a point of visiting less heralded museums. On my first visit, with my 13yo daughter, we went to FOAM and loved that, to The Old Church in the Attic, to the Dutch Resistance Museum (instead of Anne Frank, which for some reason hasn't compelled me), and we rode out along the Amstel river per RS' suggestion (just got on a bike path along the western side and made sure we stayed along the river. No map).
I also really liked Lisbon. Same thing. Its hard to put a finger on what grabs you about a place, but it did.
The Cinque Terre and Amalfi coast (and French Med.) have a very different feeling than the cities. I didnt feel grabbed by any of them but they are nice as a counterpoint to the pace and intensity of site seeing in a city, and of course, everywhere is a great place to go once.
I have been slowly moving East in my interests, so Budapest and Prague appeal to me (from your list) although I haven't been, but if you did the E. Europe segment for this 2-3 weeks, I would think about including Croatia (but that's my bucket list talking ;)

I am getting more and more inclined to visit the smaller provincial cities. They often have more character than the bigger ones, and surprise me with the most wonderful histories.
The Czech Republic has a string of these: Brno, Kromeriz, Olomouc, Hradec Kralove, Ceske Budejovice, Plzen and the famous spa towns: Marianske Lazne, Karlovy Vary and Frantiskovy Lazne.
Recently I was pleasantly surprised with the Slovenia and the area around in Italy and Austria: Trieste, Udine, Ljubljana and Graz.

I agree with tonfromleiden about enjoying the smaller places in Europe more these days and not the larger towns so much.

I just got back from my first trip to Portugal. Although I liked both Lisbon and Porto, I enjoyed my stops in smaller towns (Nazare, Tomar) far more. Those are the places I really yearn to go back to, actually.

Belgium: Bruges, Ghent and Antwerp: two smaller and one larger city. Lots of history, architecture and art. Skip London and fly into Amsterdam. Amsterdam> Antwerp> Ghent and/or Bruges (stay in both, which I'd recommend, or make one a base and day-trip the other) >Paris (from Brussels).

And Kathy forgot to mention Mechelen, halfway between Antwerp and Brussels.
In Italy Bologna is surprisingly attractive for such a big city and a perfect base for the gems around, such as Ravenna, Ferrara and Modena. In the Veneto I've a weak spot for Padova and nearby Vicenza, not to forget Mantova with amazing Sabbioneta less than an hour on the bus away.
Closer to my home cities like Haarlem, Utrecht and - of course - Leiden make a good alternative for staying in Amsterdam. All attractive without the crowds of the capital.

I loved London. I don't think you can miss with that. Great art and history. It might even displace Paris as your favorite city.

Edinburgh should be added to your list. It's a great city and May is a decent time to visit. Berlin is another you should add (I'd want to go early to mid September). Copenhagen is another city you might really like (go in July or August).

Some purely personal opinions:

Madrid, IMO, is the most skippable city in Europe. There is one great sight, El Prado, some nice park areas and a few other things worth seeing. For me it's like visiting Baltimore; they were both established in the 1600's. Madrid came into being a century after the most interesting parts (for me) of Spanish history. There is no old center in Madrid because it didn't exist. Toledo, OTOH, is a great place but probably not big enough for someone attracted to cities. Seville and Granada should be your next cities to visit in Spain but they might be really hot by May.

A'dam loses me because of the crowd it attracts. I really like the canals, architecture and museums but so many tourists are there for the licit drug and sex scene, it makes me want to get out ASAP. There are so many nicer places in Netherlands (but most are probably too quiet to meet your city taste).

As a city girl, I don't think you would enjoy Cinque Terra. It's the opposite of city. A series of relatively sleepy little towns, with very little to see and do other than relax and enjoy the scenery. Rick calls them a vacation from your vacation and that's probably a good way to describe them.

For art and history, Vienna is up there with the superstar cities. However, it doesn’t make geographic sense on a trip starting in London and ending in Paris. London and some nearby places - - - Bath, Oxford, Cambridge, even Edinburgh - - - can easily fill a week or more. I recommend 10 days in the U.K. The Netherlands and Belgium would easily fill up any days between London and Paris. Amsterdam and the IMO, vastly underrated city of Brussels are great for art and architecture. Bruges and Ghent, also.

I also vote for Amsterdam and Bruges/Ghent. We spent 9 days in Amsterdam in July of 2015 and didn't get to all on our list. We did day trips to Haarlem (reserve for Corrie Ten Boon house tour), Delft, and on the localbus.nl you can go to many small towns outside the city such as Edam ( go on a Wednesday when they have the cheese market, a great morning, very entertaining.). Bruges and Ghent would be a few days too. Scotland is also a fabulous place to visit and could easily fill your days. Wherever you go I'm sure you will have a great time.

I loved London. I don't think you can miss with that. Great art and
history. It might even displace Paris as your favorite city.

Brad, I love London too! Just thought to maybe save it for the next trip as the Amsterdam>Belgium> Paris route made linear sense, if that makes sense? Not a lot of time spent in transit. :O)

Oooh, good note about Mechelen, Ton. That's on my list for next time.

Amsterdam isn't a personal fave but a lot of folks like it so what the heck, the OP should get a look and decide for themselves. As mentioned, there are also some easy days trip from that one.

Editing to add:

As a city girl, I don't think you would enjoy Cinque Terra. It's the
opposite of city. A series of relatively sleepy little towns, with
very little to see and do other than relax and enjoy the scenery.

Arg, Brad, whatever they were once, the CT has been the exact opposite of "sleepy" for some years now. Maybe during the winter but they're positively overrun with day trippers during high and shoulder seasons. No reason not to go unless you desperately hate crowds but, well, they're not "sleepy". There are upper trails where you can lose the mob if interested in hiking, and it quiets down a bit at night when most of the trippers leave. But other than hiking, swimming, checking out the churches and whatnot, you're right that just hanging out is about the extent of it.

Definitely make it a 3-week trip and visit both London and Amsterdam. Consider some of the England day-trips mentioned and Edinburgh. Cheap and easy non-stop flights from Edinburgh to Amsterdam. You would have time to visit other highlights of the Netherlands and Belgium as you make your way from Amsterdam to Paris.

I'm a big city girl in my late 30s who also loves museums and history, so make of my recommendations what you will!

London: Probably my favorite city in the world (so far). It's expensive, but it gives me that feeling of amazement that I expected to feel in Manhattan and just never did. It's expensive, but most of the museums are free and Ah-may-zing. I've been 4 or 5 times and I would return in a heartbeat. Great food scene, too. And Londoners are surprisingly friendly. Medieval/Renaissance English history was my first big love and if you're into that, there's no way London will disappoint. You might also want to take the train up to York, it wears it's medieval history on its sleeve but still has the feel of an active university city.

Amsterdam: I had no major interest in it but we ended up going on a lark due to good airfare, and well, we returned 3 more times that year (the cheap airfare helped, but we really fell in love with it.) People who don't like it, in my experience, stayed in the crowded tourist center. If you go, stay in the Jordaan, it's absolutely perfect and so beautiful and doesn't have the drug/sex scene that you find in the center. The museum scene there is just behind London and Paris, especially if you're like me and love the Dutch masters. The cool thing about the NL is everything is very close so it's very easy to catch a 20 minute train to Haarlem (Frans Hals museum may be my favorite small art museum so far). Locals are also pretty friendly and the search for a favorite brauncafe is a fun evening activity. Plus, I mean, a little bit of marijuana can be fun, too...it doesn't have to be a seedy experience. You can hit up the coffeeshop "Abraxas" and then enjoy some bitterballen on the canal boat bar P96 in the sunshine...heaven.

Madrid: I wanted to like it more than I did. I was also on a girl's trip and there was some social friction which may have contributed, but I'm not the only person I know who was underwhelmed. The tapas scene is really cool, and if you do your research you can eat very well for the cost of a small beer in tons of places. I got out to one of the more gritty suburbs on my last day and had a more fun urban experience, the modern art scene there is quite happening. The Prado is fantastic and is the reason I would suggest trying to visit as part of a larger trip to Spain/Portugal, but I don't think you'd need more than 2-3 days in Madrid to feel like you've seen the important stuff.

Budapest: I've been twice and I like it, but some people here really love it. It's got a distinct atmosphere, ruin pubs are fun, the museum scene is a bit less exciting, but it's a great place to visit for a couple days, especially combined with Vienna.

Vienna: VERY underrated in my opinion, based on two visits. It really does feel like the "Paris" of Austria, due to the moments and palaces throughout the city, beautiful churches, and world-class museums. It's also got a hip youthful vibe outside of the tourist center. And the history aspect is amazing if you're at all into the Holy Roman Empire/Austro-Hungarian empire/WWI. Seeing the car that Franz Ferdinand was shot in and his uniform at the military museum gave me chills.

Prague: it's probably the most beautiful city I've been to, but it's hard to escape the tourist crush in the summer. I've been in May and early June and it was pretty crowded both times. The museum game isn't top notch compared to stuff listed above, but still worthwhile. Totally doable as part of a Budapest/Vienna trip.

Lisbon: Haven't been yet but everyone I know who's gone to Portugal has raved about it. Hoping to go soon. Some people prefer Porto but it's not like they're far away from each other. Hope this was helpful!

Also if you like big cities and museums, Berlin should be on your list. Plenty of cheap flights between Berlin and Amsterdam, but you can also train between them. When I say London is my favorite city, there's a part of me that whispers, "What about Berlin?" Few thing compare, IMO.

Madrid is a favorite of mine. I travel for history, art, architecture, and food. Great art museums in Madrid and other museums as well. I enjoy the elegant 1600s architecture in the center of the city. Madrid also has nice parks to take a break to enjoy nature. Good food most everywhere. You could also see pretty decent (not necessarily Sevilla level) flamenco performances.
I recommend you take the short 30 minute commuter train (same price daily, several departures ands returns) from Madrid to Toledo and spend the night there for a glimpse of older Spain. The old city is a walled city on a hill surrounded on 3 sides by a river. Picturesque.
Another very short trip (day trip only, no need to spend the night) from Madrid is Alcalá de Henares, an old town with few non-Spanish tourists. Visit the former Colegío de San Ildefonso buildings and the former home of the author Miguel Cervantes.

For art and history, Budapest, Vienna and Prague are interesting, but you may wish to do a separate trip to do those together.
I would do a week in London, 5 days in Madrid with the 2 side trips, and the rest in Paris (my favorite, too).
Have a great visit!

I'm also more of a city girl with similar interests and have traveled solo plenty. Since you want to start in London and end in Paris, and you are really into art and history, I'd pick Amsterdam.

Train it from London and start in Amsterdam. Depending when you are traveling in May, you may still be able to catch the tulip fields via a day trip just for a change of pace. Get yourself a Museumkaart which covers admission at many museums all over the Netherlands. You can also do a day trip to Utrecht (more great museums) which is small, but lively and has some really pretty canals.

For a change of pace, work your way south and stay in Rotterdam for a night or two and side trip over to The Hague - both offer great museums and Rotterdam has some very interesting modern architecture. I'd then suggest making your way over to Belgium and stay in Antwerp - more good museums, great fashion scene/shopping if you like that and want a break from all the museum hopping. You can base in Antwerp and take day trips to Bruges and Ghent. From Antwerp head to Paris to wrap up your trip.

What I loved about the Netherlands is that there are so many museums that aren't just about the Dutch Masters or VanGogh, so you can mix it up. Same with Belgium - besides all the great art museums, they also had some real gems. And if you are active, you can do stuff like biking. Yes, biking in the center of Amsterdam can be a little chaotic with all the local riders, the trams and pedestrians - but there are other places you can bike in relative peace - like Kinderdijk which is a Unesco Heritage site if you have any interest in getting some photos of the windmills.

Thanks for all the replies!