An A4000 with a 68030 CPU will run OS 3.9 nicely, with 16mb ram.
Though 16mb Memory doesn't go too far, once you get a nice background and run a few applications, especially if you're using a video card.
The problem is, with a 68030@25mhz a video card won't be all that fast, especially if you're planning to use True Colour.
As far as I know most Amiga Video cards go up to 24bit and that's it, you can usually pick up a "Cybervision 3D" for a good price, they're not the fastest around but are still a good card in my opinion :-)
Robert