Recommendations for a Parisian Picnic
1. Along the Seine. Nearby good charcuterie: Oteiza, 18, bd St Michel. Or Marché Flottant du su-ouest on 17-19 september. Quai Montebello http://www.marchesflottants.fr/
2. the many ill-known and lovely gardens in the Marais, like jardin Anne Frank, Saint Gilles-Veneur, Clos des Blancs manteaux. Nearby good sandwich places: Banh Mi place on 7 rue volta. Finkelsztajn on 27 rue des Rosiers, which I prefer to the cross-the-street L'As de blabla. Marché Enfants Rouges.
Parc Monceau is indeed a great picnic site. But be sure to get all your food at Poncelet before you get to the park. There's no there there all around the park, esp no food. Once inside the park, a can of soft drink is 2.5 euro. Try to picnic near the largest tree in Paris there, a famous Platane d'Orient.
The Buttes Chaumont is very pretty in a 2nd Empire over the top way with follies and grottos and waterfalls. There are lawns with great views over Paris where you can spread out a picnic blanket.
One word of warning. I don't know if you're planning on bringing wine or other hooch for your déjeuner sur herbe, but officially, you're not supposed to drink in public parks in Paris. If you're not aiming to get ripped, there is a tolerance for more "responsible" drinking. However there are certain parks in more "sensitive" areas - Jardin des Halles, Square Villemin, and for a few weeks this Summer, the Champs de Mars - where the police and the parkies can and do confiscate alcohol.
I don't want to sound like a picnic pooper, but you might want to buy your vittals on the Sunday before your picnic as all Parisian markets and many smaller shops are closed on mondays.
My wife and I have popped a cork in many public places in Paris and on fast trains and never once had a problem. Of course, we are discrete and old.
OTOH there is a fine line between an older couple enjoying fine wine and being seen as drunk street people. So far we have pulled off the former. Maybe it's the wine labels.