Here some average fps stats on laptops from first level, on the street (using DNRATE) 640x480 shadows on, full screen (maximum+):
Compaq LTE 5280
Pentium 120, Cirrus Logic 7543 (1Mb)
8 fps
Fujitsu Monte Carlo
Pentium 120, Trident (2Mb)
12 fps
Dell Latitude XPi
Pentium MMX 133, NeoMagic 2070 (896Kb)
12 fps
Fujitsu Stylistic 1200
Pentium 120, NeoMagic 2093 (1Mb)
24 fps
Asus L7300
Celeron 300-A, Silicon Graphics SM910 (4Mb)
29 fps
FMV-Biblo FMV-5133NA6
Pentium MMX 133, Trident Cyber 9397 (4Mb)
32 fps
Micron XKE
Pentium MMX 166, NeoMagic 2160 (2Mb)
45 fps
TwinHead SlimNote P79TE (9TE-200TZ)
Pentium MMX 200, Chips F65554 (2Mb)
46 fps
Doom is what you want (c) MAZter