IIRC Descent II (1997) allowed 800x600 and maybe higher even without a 3D accelerator, but you'd have needed a fairly powerful PC for running that. I'd kind of like to assume Quake would also have supported higher resolutions but I honestly can't remember.
By 1998 or 1999 so, when 3D acceleration was becoming more common, higher resolutions also started gaining more ground in 3D games.
Even after that, many 2D games (including the original StarCraft, I think) were still only 640x480, probably in order to avoid scaling issues with multiple resolutions.
Then there was VESA, which was standard for high-res, but slow.
Then Windows 95 came and with it came drivers and DirectX, and the driver wars moved on to 3D accelerator territory...
However, mid-90's games that did do 640x480 generally did that in 256 colours, so they already had to deal with going above standard VGA one way or another. Very few games that I can think of used the VGA mode of 640x480 in 16 colours, and they certainly weren't first-person shooters.