I, rather we did a tour with Tandem in France a few years back. Ferry to Cherbourg, back from St Malo. Didn't book a thing, just turned up on spec and usually found accomodation pretty easily. The one day we did have trouble we actually used LastMinute.com (using the UK website) and booked something in the next town along as the place we'd intended to stay at was having a festival and was packed.
French drivers, very good. Great respect for cyclist. French trains, you might think it's cheating, but if you need to, dead easy. Lastly, I don't know what your level of French is like, but they do appreciate the effort even if the pronounciation isn't very good.