Ok, so basically my car sounds like a lawnmower right now and the check engine light is on. Codes say its the O2 sensor and a misfire on cylinder 4. I'm not very experienced and just searching online isn't getting me anywhere. So here's the story, hopefully someone has some advice.

I was on my way back from a long drive (4 hours one way) and stalled the car out at a drivethru. When I restarted it, it started making the awful sound. I shut it off immediately and had it towed home. I have since changed the O2 sensor and disconnected the battery to reset the codes but when I stated the car up again it's still making the sound and giving the same codes. I don't know where to go from here. What do I tear apart next?

Car is a 96 Subaru Legacy Outback.

"Awful sound" doesn't give us a lot to work with, but let's give it a go.  The most common cause of misfires is bad spark.  So take a look at the plugs - these engines strongly prefer NGK.  If they're something else (or just ugly), replace them.  Look for carbon tracking on the outside of the  plug ceramic that suggests you've been losing spark to the outside of the plug.  Check that your wires and connectors look/feel good.  Listen for arcing where the wires pass by metal.

If that doesn't solve it, the next step is a compression test to see whether the engine internals have a problem e.g. a broken valve.