A clogged cat usually has no problems at idle, but can't pass enough gas to make power on the road. Highly doubtful that's your problem.

Without knowing the climate where you live, the first thing I would suspect is some condensation affecting your ignition system. A tired distributor cap and rotor, or ignition wires could be affected by moisture which dries up after a few minutes of running as underhood temps rise. This is the type of situation that's more noticeable in the spring and fall, when there are wide temperature swings from day to night.

Nearly all engines run roughly for the first few revs after starting cold. Is there a chance that either your engine mounts or your exhaust hangers have deteriorated, such that otherwise normal vibration results in the pipe hitting the body? Just a thought.
--
No one ever went broke underestimating the taste of the American public - H.L. Mencken