Well, it all depends on how many miles do you currently have on your car. Low/high miles usually determines the extent of work to be done.
1. Basic (regardless of milage):
Plugs; oil/oil filter(if necessary); air filter; clean Mass Air Flow sensor
2. Intermediate (also around 50k miles):
Same as above plus you need to start looking for and inspect the cooling system, belts; cabin filters; start looking for possible power steering reservoir leaks around the hoses; grease/lube suspension components.
3. Advanced (also around 100k miles): Same as above plus now you may be well advised to look at replacing at least the pre-cat o2 sensors; fuel filter; MAF; valve cover gasket (this could happen sooner in a car's life, look for leakege around 60k); Vanos o-ring replacement (again this may need to be done as soon as 40k)
Also 100k plus vehicles may benefit from a transmission filter change (automatic), differential gear oil change
This is what I've done/gathered from reading and paying attention to countless posts on the web and fellow E39 owners' experiences, of course the wallet always plays a major role on these type of deals so plan ahead and think of it as preventative maintenance not just a tune-up
I hope this helps.