Talk about the 'ol shotgun diagnosis. Everyone always says to put a cat and an o2 on it. Well....maybe. The big thing is why did the cat fail? What year is your rig? You said it has EGR so that is a Renix era rig.
High NOx can be cause by many things. Your EGR valve being disconnected or inoperative will cause you to fail big time. Also an exhaust leak before the cat will do the same. High engine temps or a lean air/fuel mixture also contribute to high NOx. If your rig is running at a normal temp I wouldn't worry about running hot just yet. Excessive carbon build-up in the combustion chamber will cause high NOx. Just putting a new cat on will probably get you to pass, but I have no doubt you will need another cat in 2 years to pass again.
What to do first? Grab your smog check report and head over to this website:
http://www.smogsite.com/calculators.html#lambda You might have to scroll down the page a bit to find the Lambda calculator. Start plugging in the info about your emission levels and percentages. Be sure to input them all exactly as shown on the smog check report. Click the calculate Lambda button and check the results by looking at the colored bar right below the calculate button. Now what this does is tell you if you vehicle is running correctly, not too rich or too lean. A lambda reading of 1.0 is considered perfect. As long as your reading is in the green section then you probably have a bad cat. If the reading is in any other color than green then you have to figure out why the engine is running rich or lean before doing any other repairs. This website is easy to use and will tell you pretty definitively what is going on in your engine. If the engine is running too rich or too lean, a cat isn't going to fix your problem. You may still need a cat, but at least you won't kill your cat and have to replace it again to pass smog next year. Oh, that's the other fun thing about being a gross polluter, you have to get your rig smogged
every year for the next 3 or 4 years.
Start there, and please report back what the calculator said. If you want to post up your numbers and I can run them to see what I think.