The Deneb is a great addition as you can also use most modern USB addons - printers, flashdrives, card readers, mice, keyboards, and USB ethernet dongles, which will get your A4000 on the web without the need for an X-surf or another other card.
The other upgrades are going to set you back a bundle, but depends on your definition of expensive.
When I blew the dust out of my A4000/030, which I bought in 92, the first thing I added was a DVD drive. From then on I've added:
1. CS MKII 060 128 MB Ram (bought on eBay almost 2 years ago)
2. Cybervision 3D (eBay)
3. Cybervision 3D scan doubler (eBay)
4. Upgraded the kickstart roms (Amigakit)
5. X-Surf 3cc (Amigakit)
6. 80GB Hard Drive on the X-surf IDE Header.
7. OS3.9 BB1 & BB2 (Vesalia)
8. Deneb USB (Amigakit)
9. Internal flash memory reader (ripped from my PC and fitted in the second 3 1/2 floppy bay - modified the front facia to get it to fit).
And now I'm pretty happy with what I've got. The only upgrade I'd look at could be to repalce the MKII with CSPPC, and move to OS4.0 Classic. But the CSPPC cards are way too expensive - would rather buy a SAM440 and run OS4.1, if I'm forking out for a CSPPC off eBay.