I’d cross out La Tupina. Bordeaux has an excellent dining scene, but I’m more familiar with other places in the region like Au Lion d’Or in Arcins (Médoc), a very unique restaurant like they don’t make them anymore. As is the more modest Auberge des Vignes in Sauternes.
Whenever I’m in Bordeaux, I go either to La Brasserie Bordelaise for entrecôte or Le Petit Commerce for fish, oysters, and white Graves wine. I try never to miss that fantastic ice-cream place named Del’Ice and Coffee" on Quai Richelieu. The fraise du Périgord flavor should be in season now, it is not to be missed. One thing is certain, you’ll never go hungry in Bordeaux, I think it is the French city that has the highest ratio of restaurants per inhabitants.
Turning tables is not rare in Paris but it is a new trend and not really a French habit. At most restaurants, you have your table for as long as you wish. Some restaurants count on early reservations for tables being freed around 9-9:30 PM and they can accommodate other guests, but as a rule you won’t be kicked out.
Pétrelle is more a romantic place than one where you’d want to take a toddler, although I’m sure they’d welcome yours.
Don’t mind what I said about Parcelles if it’s convenient for you, it’s a very fine restaurant. Just not the kind I’m attracted to.
I had no idea Papillon had closed; I might pull out my Arabian phone (French colloquial expression which means word-of-mouth in a given professional context) and see what may have happened to Christophe Saintagne, an excellent chef by all means and a lovely person.
Terroir Parisien was not far from where I live and I just loved that place. It was also the only affordable place Alléno ever created. Too bad, now he’s exclusively catering to the very rich.
Le Mazenay, yes of course, it’s a no-brainer. In the 8th I’d recommend Le Chiberta, which has been recently taken over by Clément Leroy, one of Guy Savoy’s best chefs. In the 16th I’m not sure, there are many good places but none comes to my mind right now. Bistrot Flaubert has a good reputation, I haven’t been there since it changed chef (several times around, really).
If you’re staying in the Haut Marais, you might look into the very charming & friendly contemporary bistro, Bistrot Instinct on rue de Picardie in the 3rd.