Ooh! I installed MuRedox, and now Duke runs a LOT faster... its completely playable now. At the default size (fullscreen, except status bar), it averages 20FPS, and gets 46FPS if I face a wall. Mirrors and overlay text give that a big hit, though. If I shrink the window right down (not that I need to; its perfectly playable fullscreen), I get nearly 80FPS facing a wall, and 60 odd average.
My setup is A4000, Cyberstorm MkIII 060/50, Mediator 4000, Voodoo 3, Repulse soundcard via AHI. It works great!