I was in St. Malo only briefly over 30 years ago so will not comment on that area beyond saying that you should definitely check historical weather data, especially rainfall stats. (Actually, I think you'll find that there's considerable potential for chilly, wet weather in all the places you've mentioned in early April.)
The other spots I've visited during my current trip. I'll try to add to what others have said.
All are worth visiting, most definitely including Lyon. It has the old medieval district as well as the newer but great- for-strolling Presqu'isle, churches, museums, etc. Quite a lot of indoor attractions (not to mention the restaurants), which would be very handy if you had a rough early spring.
I actually made a quick second trip back to the Reims Cathedral to look at the modern glass again. The next-door Palace du Tau houses some treasures from the Cathedral. There are some promising-looking restaurants located near the covered market. The aforementioned Roman gate was swathed in something that made it totally invisible a few weeks ago and there was no evidence outside that wrapping of any work in progress. I do not know whether it will be unwrapped by next spring. The Musee des Beaux-Arts is worthwhile. Some sources say it is currently closed, but the planned work was canceled or postponed. There's an interesting exhibit of art nouveau/art deco furniture and some decorative objects on the ground floor. Otherwise it's mostly paintings, with (I think) some glass. While not disputing that there's some interesting architecture in Reims, I thought Nancy was a better place to see art nouveau at its source. Reims is clearly prosperous (buildings in good repair, etc.), but not outstandingly attractive by the standards of France as a whole. I wouldn't particularly recommend it for someone uninterested in the champagne houses, despite the sights I've mentioned.
Colmar does look German to my uneducated eyes. To me it is drop-dead gorgeous, because I love half-timbered buildings. The Isenheim masterpiece is stunning. I visited Nancy immediately afterward and thought that was a good combo, architecturally. I had quite hot weather, but you'd be more likely to have the opposite problem. I think there's enough walking to be done (the other tourists are fairly concentrated, leaving much of the historic area pretty untrafficked) to fill about two days in conjunction with the Unterlinden Museum, which is quite large. You could also visit one of the smaller towns. I found Selestat (also half-timbered) pleasantly untouristy. And of course there's also Strasbourg. Normally I'd have opted to stay in the larger city, but hotels in Strasbourg seemed a good bit more expensive than those in Colmar.
I visited Beaune as a day-trip from the larger Dijon. It's attractive (handsome streets for strollimg) but I thought one day was sufficient for someone not interested in wine. I'd pair Lyon and Dijon and side-trip to Beaune.