Tune up change sparkplugs

Check that you have the proper air pressure in your tires. Change the air filter. If you're constantly hauling a lot of people or stuff, the extra weight will lower fuel economy.
Next go with a tune-up- new sparkplugs and wires.
You may also want to look for a small fuel leak. This could be particularly dangerous if you have one. If it is a fuel leak, don't drive the vehicle until it's repaired.

I usually service Ford family Brands and will try to assist you. Back in 1995 there was a change to longer service life sparkplugs and the elimination of Distributors with Crankshaft sensor firing of the plugs. It really depends on the Manufacturers' idea of when to replace sparkplugs by mileage and the various filters on the engine.

You can install plugs and filters anytime you want; just a matter of prematurely spending money on something you do not need. Air filters 12,000 miles, Sparkplugs 50,000 to 100,000 miles, Serpetine Fan Belt 40,000 to 45,000 miles, Fuel filter 25,000 to 45,000 miles.

Check with Autozone, Advance, or Oreilys for information about Manufacturers specs. Stay on an oil change interval based on your driving habits. Sometimes oil breaks down without higher miles and you need to change by date rather than by use. Clean oil for Winter starts, clean oil for Summer driving. Twice a year is adequate for low mileage. Watch your Antifreeze, it chemically changes after 3 years and loses corrosion inhibitors.

I hope at least some of my suggestions are useful to you.

Try running fuel injector cleaner through the gas tank. A fuel injector might be stuck open, letting lots of fuel into the engine. Also try replacing your fuel pressure regulator, and inspect the fuel tank return lines.
Good luck
Matt

Oxygen sensor only report the condition of the engine the rough running condition can range from a worn sparkplug wires to worn sparkplugs to valve problems to injector problems. with the cadillac deville a tune up should be the first attempt to smooth the rough idle with the inspection of the cap and rotor cap and rotor do have a tendancy to arc internally and create misfire so does sparkplug wire that can leak spark voltage to ground and create misfire. the spark plug wire especially if they are brittle and hard can create issues

Needs an oil change, and a tune up, pressure wash the engine well, and replace all filters. It's an old maxima, it's seen it's best days.

may need a tune you change wires and sparkplugs and you'll get better gas miliage too and you might want to get the timming checked

If it was the head gasket that you replaced, it may be fractionly thicker than the original so the compression has dropped. (I have done this myself before).
I could be wrong but its worth a thought

replacing air and fuel filters, pcv valve, sparkplugs and sparkplug wires, cleaning throtle body, thats it, note getting to rear plugs and changing them is a job need a lot of patients, may have to remove wiper bucket, to make it easier to get to rear plugs good luck make sure you use double platnium plugs, costly but correct plug, good luck.

first you need to know what size the engine is in canada its metric , how many litre? in the u.s. its cubic inches. is the engine a 4cyl. , 6cyl. or 8cyl. most tune ups nowadays consist of sparkplugs and sparkplug wires , and like the other you need to know the size of the engine. its better to go to a oil change garage when they have a special deal on.

give it a complete tune up and change the fuel pressure regulator and check the timming gear