Toyota Repair: Tacoma Starting Trouble, fe engine, toyota parts

Question
I am the original owner of a 95 Tacoma with the 2RZ-FE engine, 2.4 liter, 4 cyl, 2 wheel drive, manual transmission with 85,200 miles.

This Summer I have been experiencing a very frustrating problem. The truck starts fine in the morning but if I try to run an errand at lunch the truck intermittently experiences a long crank before it starts. Sometimes it just
cranks (strongly) but I stop so I don't damage the starter or battery. Since it's a manual trans I just push it to get it to start. I have learned to pick "strategic" parking spots in case I have to push it to start it. Push starting
has worked every time. The problem seems to appear after the engine gets hot, or during the heat of the day (we've had a heat wave recently in NJ), or if I am only in the store a few minutes and the engine hasn't cooled.

Recent repairs to try to correct this problem include: 'Shop A' did a tune up (air filter, distributor cap, ignition rotor, ignition wire set, spark plugs) but referred me to 'Shop B' after the problem persisted. At visit one to 'Shop B', they replaced the (NAPA) fuel filter with a Toyota filter and replaced the distributor rotor with a Toyota rotor (this guy is a believer in original Toyota parts); at visit
2 to 'Shop B' they replaced my upstream O2 sensor because the check engine light coincidentally (?) came on during a day that the problem was happening unusually frequently. Thankfully, I was close to 'Shop B' and he checked the codes: the error codes were PO130 & PO133. Unfortunately, the problem is still
happening.

Oh, about a month ago the dealer replaced my ignition because I couldn't get the
key to turn. I'm not sure if that matters, but I wanted you to know.

I scanned some of the previous answers provided for similar "hard starting" questions. When I turn the key the check engine light does come on, then disappears when the truck starts. That seemed relevant information to other queries, so I thought I'd tell you. Also, 'Shop B' seemed surprised when I told him the truck starts when I push it. His comment was that that ruled out a fuel problem, that he thought it was electrical.

I appreciate your help.
JT

Answer
The check engine light is doing what is supposed to under normal conditions it will be on until the engine starts and then turn off.
Since replacing the O2 sensor did not help there may be a problem with the engine which may have caused the engine light to turn on, at this time I would recommend having the engine compression tested to check for a weak or leaking cylinder, this is not uncommon on these engines.