Plastic coffee can lids for plates. Magellan's has packable wine glasses which are a little pricey. Don't forget a corkscrew. Pick up a knife when you get there as it won't pass security. Throw in some wash'n'dries for good measure.

I have some diamond brand super strong plastic dinnerware that I use for trave. I call them industrial plastic.

They can be washed numerous times, the knives will cut things and not break. I believe I picked them up at a Target.

I've used these utensils for the past 15-20 years, and like them a lot.

You can also get picninc supplies at a 'supermarket' wherever you hapen to be. I've done that many times.

Plastic table covers from the Dollar Store... use 'em to sit on the ground or cover a not-so-clean bench.
You can carry on a corkscrew withOUT the little blade *unless* you're flying on Air France.
I used to take unbreakable wine glasses but still a bit bulky, so now I take a stack of the 'wrapped' plastic cups hotels/motels provide.
I use the plastic coffee can lids as 'plates' (more like saucers).
I scarfed two sets of the 'plastic' or hard-molded dinner ware the airline provided with our meals - - can be washed and reused, sturdier than typical plastic forks/knives.
I pack a lightweight nylon tote (either packs flat or into its own pocket) and we use that with all the above stored in it once we unpack at the hotel.

I just make up my own 'kit'. All you need is some plastic silverware, one plastic plate per person, a few plastic cups, paper or cloth napkins, corkscrew, small folding knife. Put them all into a 1 gal. ziplock bag. Voila!

If you have an outdoor gear store nearby, check it out. They have all sorts of stuff for backpackers who are very concerned with packability and weight. For plates/bowls, there's the folding style option, the ultimate in easy packing as they unfold flat. Here's a link to one style being sold at my local outdoor gear store:

http://www.mec.ca/AST/ShopMEC/HikingCamping/CookwareUtensils/PRD~5029-246/fozzils-solo-pack.jsp

You can use them flat as well if you just want to put some cheese, bread, meats etc. on them.

The good quality plastic utensils are a good suggestion. You can also get travel utensils. If you don't want to buy a whole box of plastic utensils, you can also get individual sets at outdoor stores:

Cheap: http://www.mec.ca/AST/ShopMEC/HikingCamping/CookwareUtensils/PlatesCupsBowls/PRD~5016-551/gsi-gsi-tekk-cutlery-set-acetal.jsp

More expensive: http://www.mec.ca/AST/ShopMEC/HikingCamping/CookwareUtensils/UtensilsAccessories/PRD~5025-227/alite-designs-inc.-coverware-cutlery-set.jsp

When you said a "handy little mat", were you thinking of something to sit on or put your food on or both? For sitting, there's these types of options for sitting on the ground and also nice for benchess that are wet, dirty or cold:

http://www.mec.ca/AST/ShopMEC/HikingCamping/SleepingPads/PRD~5024-698/zotefoams-blue-foam-bum-pad.jsp

http://www.mec.ca/AST/ShopMEC/HikingCamping/CampingChairs/PRD~5027-424/therm-a-rest-z-seat.jsp

Depends the park, but I know some, like in Paris, you aren't supposed to be sitting on the grass, so I don't think you'd even need a "mat". In the hotel room you'll have a table or can use a bathtowel on the bed.

Plus for me usually a 'picnic' comes about spontaneously during the day, I wouldn't want to be toting a bunch of extra stuff all day just for that.

had my corkscrew taken awaay from me at secruity as it is considered a weapon so I don't botheer unless I am checking luggage. they are cheap enough to buy and some hotels have them in the room that you can certainly use and take to the parks, etc. just remember to put it back. We have a little kit that has a small wooden cutting board and place for plstic forks, spoons and knives. Can't bring the knife that goes with it as again - a weapon. We take it everywhere so we can have cheeese and crackers inour room, or on a picnic when we travel.....You can put together one yourself. i like the idea of coffee can lids as small plates - smart - think I'll put a few in my travel kit....

Why use something as a plate when semidisposable plastic plates are easily available in the grocery store? A pack of ten or twelve takes very little room. I found a plastic corkscrew (actually a pack of two) for sale a while back, so that problem is solved. Plastic cups for beverages just like the plates. The cups hold the plastic cutlery, paper napkins also serve as tablecloths, and you're done. Of course, if you fear the TSA, just buy stuff at your destination and discard before heading home.

Buy stuff once you get where you are going, especially if you are going carry-on only.
You can get semi disposable plates, plastic glasses (or even cheap glass ones), a cork screw, utensils, everything you need from a supermarket on arrival.