1998 had plenty of 16MB video cards (TNT, Banshee). There's also the AMD K6-2 500MHz. Counter-Strike first came summer 1999 and the P3, Voodoo3 and TNT2 were already in full swing.
When Counter-Strike released 1.3 in 2001, it included 512x512 textures for player models so the 16mb VRAM requirement is more about those.
Most of Counter-Strike's performance issues stem from texture switching in particular with weapon models and animated sprites (especially large amounts bullet impact smoke). It was worse in earlier versions when each player model had like 4 different textures each, the 1.0 update resolved that with new single surface meshes. And of cousre the infamous smoke grenades that cause fillrate issues especially for unfortunate Rage Pro users......
Counter-Strike 1.6 today would require Windows XP and a P4 to run because of the Steam minimum requirements.
I've had CS 1.5 (last WON version) running on a PCX2 before, and that's way under 16mb 😀