Check out the mpg sticky in the second gen forum: http://legacygt.com/forums/showthrea...ps-167968.html
I'd still replace the air filter. A good idea is to replace the air filter, fuel filter, all new plugs (I like NGKs), new wires, new pcv valve, clean the throttle body. Do you have any CELs? I get about 20-22 city and 27ish highway. Check your injectors, and ignition coil. Clean your MAF sensor too.