Why does potential chemical energy decrease with increasing oxidation of carbon?
is there an intuitive explanation of why increasing oxidation state
  correlates with lower potential energy, at least for carbon?


The heat of formation of methane, carbon dioxide and carbon tetrafluoride are -74.9, -393.1 and -927.2 kJ/mol respectively (the trend remains unchanged even if you divide by MW and compare per unit mass).  As we shift electron density from electropositive elements to electronegative elements we stabilize electrons, their energy is lowered.


  Does increasing oxidation state correlate with lower potential energy
  for all elements?


I haven't checked extensively, but the trend seems to hold up.  I'd expect it to hold up.

$\ce{BeH_2}$, $\ce{BeF_2}$  127.2, -796.7 kJ/mol

$\ce{CaO}$, $\ce{CaF_2~~}$      39.1, -789.1 kJ/mol

$\ce{NaH}$, $\ce{NaF~~}$      126.2, -288.0 kJ/mol


  Why does it seem that oxygen forms rather strong bonds with other
  elements in many cases?


I'm not sure what you mean by "strong bonds".  The C-O bond in carbon dioxide is much more reactive than the C-H bond in methane.  Perhaps you're alluding to molecular stability which takes us back to the top, e.g. compounds with polar bonds typically have stabilized electrons, electrons in lower energy orbitals, as discussed above.