O2 sensor is a separate problem that will effect how it runs and fuel mileage, but has no connection to starting system.
You'll need Volt/ohm meter to test your wiring. HF has them for around $5. Not super accurate, but it'll tell you if a wire is OK. Better meters are available for whatever you're willing to pay.
Most common cause is a faulty starter solenoid, but if it is bad there is no way to actually test it. You can use the volt meter to see if 12V is getting to it. There are 2 wires that actually go to the solenoid. Which is on top of the starter. The big one always has 12 volts since it's connected to the battery. You need to see if the smaller purple one is getting 12V when someone turns the key to start. Be darn sure it's out of gear. If it's getting the 12V at that end of the purple wire and nothing is happening the usual route is to replace the starter and solenoid as a unit. They're available separately if you know where to look, but unless you're good at this stuff just replace both as a unit.
If you're not getting 12V to the starter solenoid wire,there are a number of things between the key and the starter.
One of which you've already replaced. Sure that is installed correctly so that it makes contact when the pedal is depressed? It will have 12V to one wire until you depress the pedal, with the key turned to start. Then both wires should have 12V. The one to it and the one from it to the relay. Have you checked the IGN A and CRANK fuses in the underhood fuse box (UBEC)? You can also try swapping another identical relay from one of the other positions to test that. Long as it's the same number it'll work.
A 2000 2.2 manual S10 starter wiring diagram would be helpful. I think I deleted all reference to automatic trans and 4.3 engine to simplify this:
View attachment 371123
View attachment 371124