since heroes 3 has been mentioned a lot and i've tested it quite a bit, i'll just add my two cents: using a matrox millennium the game ran similarily poorly on a 200mmx and k6-233, i'd say on those specs it'd be technically playable but would get old quickly with all the hitching and waiting forever for enemy turns, so if i'd have been stuck with this experience back in the day i'd just have kept to heroes 2. on a pii 233 it ran quite a bit better to where it was still somewhat more stuttery than on "fast" hardware, but seemed like a workable minimum spec for the game. as to why the pii did so much better than the sometimes equivalent k6, maybe it's due to the better cache/memory or PCI performance? it's clear the 800x600@16-bit engine is a big upgrade over the previous game, they really should have printed pii 233 as the minimal spec.
it's interesting how testing some of these games on old hardware uncovers certain very specific effects that one would never think about today but were actually demanding on period hardware; in heroes 2/3 picking up resources becomes really slow, likely due to a transparency effect being used, while in master of orion 2 the post-combat planet bombing is seriously unresponsive for some reason.
also a 2 meg card is quite adequate in theory for directdraw games into the 2000s, in practice driver support might be problematic though. for instance i recall that the millennium runs diablo 2's directdraw mode with glitches, perhaps because the latest drivers for that card are nearly two years older than that game... so i don't know how s3 or even obscure chipsets might fare, even though on paper any card with vision964 or better performacne should be fine for something like heroes3.