O2 or Cat's on 2nd Gen Fronty 4L

The front are "technically" air/fuel ratio sensors and not oxygen sensors. They look similar, but the air/fuel ratio sensors work a little differently and are a lot more expensive, unfortunately. When they fail, they "usually" trigger a trouble code (note the "quotation marks" on "usually"). They also work in a very narrow range, so they can be very hard to test even if you do have an expensive scan tool. Upstream catalytic converters due fail quite a bit on the 05-and-later Frontiers and Xterras with the V6 and the R51 Patfinders with the V6. More often than not, if you have only a catalyst efficiency code and no other codes are set...and assuming you confirmed that there are no leaks in the exhaust system...it's usually the converter, itself. That said, if you are smelling fuel in your exhaust, it might be worth checking into a little further before dropping a couple hundred bucks on a converter. I would start pulling the oil dipstick and checking for a gas odor and/or an overfill condition. If there is, replace the oil and filter and so a compression test, fuel pressure test and fuel pressure leakdown test. Leaking injector(s) or excessive fuel pressure, albeit not common on the VQ40DE, can cause a rich condition and also ruin a catalytic converter. I've already read about a few VQ40DE engines that have had an upstream converter come apart and cause scoring of the cylinder walls and low compression, similar to the early QR25DE engines in the first years of the L31 Altimas. As far as aftermarket converters, Walker is probably one of the best out there. I have one on my '06 Pathy and haven't had any problems so far. If I was going to replace the front converter, I would replace the front air/fuel sensor regardless.
As far as O2 sensor removal, once you get the plastic wheel well liner out of the way, it's really not to bad as far as getting the sensor out of the exhaust. The hard part is getting to the latch-style connector and getting it apart and re-connected. I use a short-style sensor wrench on these.

Well, it makes sense that it would be rich at cold start-up, as it should be. All you need to do to check for exhaust system leaks is have someone with a wet rag block of the end of the tailpipe with the engine running, causing back pressure. If there are any leaks, you'll be able to see and hear them.
Rust is always a pain when working with exhaust, however, Nissan exhaust bolts are usually pretty strong and sometimes an impact gun and a little heating with a torch will get them out. The real pain is that the heat shield covers the front bolts of the upstream converter and if you try to remove the shield, the bolts almost always break. So, most mechanics will trim-off the end of the heat shield that covers the bolts for access. You will need to remove the mid-pipe/downstream converter first, which is bolted to the back of the upstream converter. Remove the front wheel and plastic wheel well liner to access the front bolts/nut of the upstream converter. You will want to order some new plastic clips for the plastic liner as you almost always end up breaking a couple trying to remove them. You'll also need some new pipe gaskets, as well. Once you get the upstream converter unbolted, it can be removed from the bottom of the vehicle. Of course, don't forget to unplug the air/fuel ratio and oxygen sensors, first.