I looked at this last night and I guess I was too tired. Its really very hard for me to answer this question as the simple first step is beyond most every one asking this question.
There is NO way that car would fail those standards without severe failure of the feedback control system (and catalytic action as a result). Since the first step is to monitor that system its very hard to give advice.
Since its unlikely that a real diagnostic can be done at home, my advice would be to replace the O2 sensor (if 115,000 miles old). If there is a misfire at idle I would replace all the plug wire ends. I would do this because its not bad maintenance and might grab the problem. I wouldn't waste any other funds till the system can be evaluated. If you want to evaluate the system view the article in the DIY section and ask any questions that come up.
Bosch Master, ASE Master, L1
33 years MB technician