I second the Travel Contacts.I have ridden the GAP & C&O in late October the last 2 years and parts of the trail were dry and parts VERY muddy. The Travel Contacts worked GREAT. They were good for the time riding around DC on pavement.
FWIW I ride a Giant Escape hybrid with 700X32 tires and fenders for this ride.