I always snark that "if you've seen one Christmas market, you've seen them all." They're all very similar, just varying in size. On top of that, I just don't get the appeal - standing outside in the bitter cold with everyone power-smoking around you is definitely not my idea of fun. After an hour or two, at most, I am always more than ready to leave.
But, I'm not a total Scrooge so I would recommend the bigger cities in Germany - Munich, Nurnberg, Koln, Berlin. In my area, some of the smaller ones are good - Heidelberg, Trier. I really enjoy visiting Rothenburg too. In France, Strasbourg is my recommendation, with a side trip to Colmar. Luxembourg City was a surprise too.
Some cities have multiple markets throughout. Munich has the main one in front of the city hall in Marienplatz but there are other, sometimes more interesting, ones too - there is a nice one in the English Garden, one with ice skating in Karlsplatz, a medieval themed one near Odeansplatz. Berlin has a bunch of them too, with the nicest one being in the Gendarmenmarkt.
Pick locations that you want to visit for some other reason - sightseeing, museums, skiing, etc., and then stop by the Christmas market as something to do after dinner, for example. I love big cities because there is so much to do, but when I think about European Christmases, I picture Bavaria and snow-covered Alps - maybe somewhere like Garmisch-Partenkirchen.
For planning purposes, keep in mind that most markets (the markets in Germany, that is) are only open until the 23rd. Stores and restaurants will be open on the 24th but usually close early, around 1600-1700, since Christmas Eve is the big family celebration in Germany. Pretty much everything will be closed on both the 25th and 26th, except for the stores in gas stations.