With you on progression. First time you see someone being super fast you call them a cheater. Then you learn about Strafe jumping and that it's just how q3 physics work (even if unintentional from the programmers perhaps) and you learn it suddenly you're called a cheater by n00bs. Same with jumping onto things of a certain height. If your graphics hardware could not do a certain framerate constantly it was impossible to do those jumps. Get a new graphics card that could render at the full frame rate cap constantly and you could literally just hold the forward key in front of that obstacle and jump and you were there. Someone with worse hardware would obviously call you a cheat because it was impossible. So at least back then it was also a hardware thing. Another one: I had a regular PS/2 ball mouse. I was just unable to do certain things. Until someone told me there was a setting in Windows to change the scan rate, which improved accuracy and also a USB infrared mouse. Huuuuge difference. In fact I still use that USB mouse today.
I bet this is the same in most games and many many "cheaters" just aren't.
Using a black skin that's part of the game is not cheating if you ask me. Editing a skin to have a bright pink that didn't exist in the game however is cheating.
Having played q3 back when myself it was standard though to make _all_ skins be the standard blue skin. The one that came with the game itself originally. That could be considered not cheating and being an anti-cheating technique. I'd say it's something that depends on the game though. Q3 wasn't really about shadows and using your surroundings in that sense because it wasn't set up for realism. You also played with gamma pretty high etc.
Something like Counterstrike or say Ghost Recon however I would very definitely find it cheating if you changed all skins to be the same because of the realism involved. Choosing the right outfit for a map would be part of the game.