Would it be possible to have trees sway by giving them several different positions and have them play on a loop? (Similar to how water shimmers and monsters take steps). This would give the game world a much more dynamic feel.
You could also make wind louder and trees sway more when it gets stormy outside.