Your milage is probably directly related to the O2 prob. Usually the primary O2 will cause the poor fuel milage, b/c the secondary one is a feedback. If there is like zero cross count on the 2nd one, then that could also be a problem. The filter won't hurt and you said it's due. A big cam will cause low vac. I don't think that's your problem there. You probably just have an intake gasket leak or a vac line that is still leaking.