Answer to old chestnut: ten trees
Plant them in the shape of a pentagram, roughly as shown below:
o o o o
To plant 16 trees in 15 lines of 4, draw a smaller pentagram in the inner pentagon of the first pentagram, and plant 5 trees at the new vertices thus created, and plant the last tree in the center of the whole figure. You'll have 10 lines of 4 that are lines from the pentagrams, and 5 lines of 4 through the center.
A diagram of this is at http://members.bellatlantic.net/~devjoe/16in15linesof4.html . (But I won't try to draw it in ASCII; precise positioning is required.)