I would do it in this order:
Use premium gas
hopefully you have deleted the CDV? MUST DO (see my signature) $30 if you do it yourself. Save your clutch AND snappy shifts.
Clutch stop ($40) screw in install
Added software will give you maybe 10-15 hp for about $400. Mine gives me 13 hp (dyno results) with no other mods. Check out DINAN
I'm not a disciple of the cold air intake for this model but some people swear by it (about $150 can get anywhere). Mine's a 98 so I'm not sure where the actual intake is on yours but I feel that mine is very good. Now a RAM air intake is a different story but requires the intake face directly front. I saw one guy with an E39 like yours take out his right front fog light and route the intake there....seems good but be careful of water intake from the road. Depends on your bumper/lights.
Front and rear upgraded M5 sway bars (couple hundred each?)
ALL of the above for maybe $1000 (plus labor for sways??) will give you some noticeable advances!!
More money?
Lightweight flywheel $800 plus install labor (upgrade clutch at same time!!)
It's all more money for less gain from there, exhaust, suspension, fatter (LIGHTER) wheels/ tires (275/35 rear, 245/45 front)?
If you are interested in stopping then a big brake kit upgrade (capliers, pads)