While the graphics are/were crude, the sheer number of polys and the dynamics of the world and layers of drawing wasn't possible in the early 2000s. Not in first person at any rate.
Look up Ken Silverman's Voxlap engine from the early 2000s. It was most famously used for the game Ace of Spades 0.75 from 2011. It had very basic graphics and I remember even at the time it was advertised as being able to run on anything. I can imagine a game resembling Minecraft being feasible on high end machines in the early 2000s