Miss or Stuttering up hills no CEL

If it were misfires you should see the master warning light (red triangle) flash rapidly. You didn't say that was happening.

The only other thing to guess at is pinking or some other engine-related problems.

Do you have any trouble code to share? Even without lights on the dash, there might be some pending or history codes available. That would eliminate the guessing, or at least cut it down dramatically.

If you don't have a scan tool but there are dash lights on, see this post for more information on how to get trouble codes.

 

I am not sure the master warning light will flash rapidly for a misfire. I think it's the check-engine light that does that.

Not for every misfire. Based on the RPM and load, the ECM calculates the amount of unburned fuel going into the exhaust because of the misfire. If it would be enough to destroy the catalytic converter, it flashes the check-engine light. If less than that, it just lights the light.

 

That new O2 sensor may be running the engine a bit lean. That being said; check fuel trim #'s, fuel pressure. Have you done a leak-down test on each cylinder, of that well worn engine. Has the fuel pump or fuel filters ever been checked, when was the last time you ran injector cleaner through your fuel system?