Does anyone else have this problem, the characters skins seem to be moving, it doesn't affect the gameplay just looks a little unusual.

It seems to me that it's just the game engine. I had this "wobbling" on GeForce 2, then the same was on GeForce 5600.
Maybe it was made due to visual damage effects like bruises, I don't know, but it never bothered me.

Everyone has this problem, its due to the MD2 model format used in Quake2 and most of the engines based on it. It uses a single byte to store vertex coordinates fo the models which doesn't have enough resolution to represent the exact pose, and animation is done via interpolating multiple frames (instead of bones that are used in most modern games) which when combined with the missing resolution has this result. It wasn't much of a deal back in the Quake 2 days, but as the rendering resolutions increase it becomes more and more noticeable.
Unfortunately there is nothing that can be done about it, unless someone has the game's source, the original models with their animations and a will to modify the model format to use floating point numbers :-P.

Would lowering the resolution or changing to software mode (is there a software mode ? i can't remember) make any difference ?

Yes.

it's noticable at all resolutions to be honest... as stated limitation of the engine
i noticed it even back in 1999 running on an ATI Rage Pro turbo at 640x480

Even when the game came out on disc, it did the same thing. Never bothered me. I thought it was kind of cool when the game first came out, like it was some new, great, advanced graphic technology.
But, then again, I was used to games like Duke3D and Blood. So, basically anything that was really, actually 3D was amazing to me.

yeah i know the feeling... before kingpin the only FPSs i played that were fully 3D were quake and jedi knight
even quake 2 wasn't experienced until after i got my hands on the kingpin demo
quake used essentially the same animation system but the models were so low poly and you never really got to get closeup views of them because they were trying to kill you and there were no cutscenes
jedi knight didn't have the wobbling because it used a very different animation system but as a side effect the character models took on a segmented look (they also had a very low polycount)
of course all these animation systems are dinosaurs in a world where physics based procedural animation is starting to slowly take over

Yeah, i remember noticing it back then and thinking "what the hell?!" xD

I think it's hilarious, makes it look like those TV shows when bugs are crawling under people's skin. (Seriously warped humour here.)

Man I don't remember it doing that, I thought I was tripping. Glad it's normal :P