I have been researching an upcoming trip to those exact two cities, so I look forward to the responses. I can't vouch for any of these personally, but they have been recommended by Rick Steves, other food/wine boards, or the "gite" where we'll be staying.
Strasbourg: Restaurant Au Pont du Corbeau, 21 Quai Saint-Nicolas. Local, organic, good wine list.
Colmar: JY's, 17 Rue de la Poissonnerie. Michelin *, modern.
Sorbetieee d'Isabelle La for ice cream.