Good suggestion to eat around the Gare du Nord. You'll be getting there in time for lunch, which you'll have time to enjoy before heading for the Gare St. Lazare. I personally would enjoy a leisurely fancy lunch a bit less because of worrying about making the connection, traffic jams, etc., but that's just me.

Terminus is old fashioned and good -- the one time I ate there I was competing for tables with food professionals in town for a conference. I haven't yet tried Chez Michel but it gets good marks. It's normally best to reserve but if you get there right at noon you'll probably get a table, especially at Terminus.