A stock A4000 will be a bit sluggish with OS3.9, but not too bad, provided you don't try a 256 color workbench. ;-) I ran mine in 64 color and remember it being reasonably crisp. 32 color, even more so.
An accelerator card that has the RAM local on it speeds up an A4000 quite a bit (it has a nasty RAM bottle-neck). After that, a graphics card really flies. I'd second getting one of the Cybervision 3Ds. They're relatively cheap (compared to the astounding prices of the CV64 and P-IV) and you can get the scan-doubler to have the same slick integration of the higher-priced cards. (If you don't care about slick integration, a Mediator or Prommy and a Voodoo PCI also offers a low-cost solution.)
