The rotten egg odor is sulfur (hydrogen sulfide to be precise). A lot of sulfur additives in gasoline these days and usually if you get that rotten egg odor in your car then there is an issue with the combustion cycle and the sulfur is not getting completely burned. Here's what I would do (one at a time) in order of expense/complexity:
1.Once this tank of gas is gone, switch stations and see if 'cleaner' gas (less sulfur additives) helps. Once you get clean gas go for a long drive on your favorite highway. Sustained high speeds and heat build-up in the cat should burn out any built up gunk in there.
2. Check/change air filter if it's dirty.
3. Tune-up (plugs/wires).
4. O2 sensors (do you have a CEL?) may not be working right and thus fuel not burning correctly.
5. Your catalytic converter is toast and needs to be replaced.
These are the run of the mill solutions off the top of my head. Your problem may be more complex, but hope this helps! GL and keep us updated.