Given this description of the engine's condition and its slightly rough
idle I'd check for a small vacuum leak. That could be a split hose or a
leaking intake manifold gasket. I say that because too lean an air /
fuel ratio at idle will cause, as you say, roughness which is poor
combustion resulting in excess HC at idle. As the engine speed increases
such a vacuum leak, being constant, becomes less and less of a factor
which could explain the emissions test result.
Another idea: dirty fuel injectors, add a can of TECHRON or equivalent.
Again, replacing the cats would be my last resort for if the cats were
bad the emissions at speed and during acceleration would be excessive
IMHO but they're not.