Fuel economy, idle, emissions problem -- please help (long)

[probedude]

Well, I would have said you need to check your base idle but you did that
correctly from your description. Check and clean your AAC valve (controls
idle speed), it may be sticky.

About the emissions
You did all the right things - EGR lowers combustion temps which lowers NOx,
as does retarding the timing.  You say the EGR doesn't stay up.  Are you
testing this at about 2200 RPM?  Can you tell if the exhaust hose to the BPT
isn't clogged.  You mentioned you cleaned it, but is it clear all the way?

About the fuel economy, is the poor economy before you changed the O2
sensor?

Lastly, have you checked your MAF grounding?