If you want make-up, Sephora has a make-up kit special for the holidays that seems really nice, it comes with tons of eye shadows, blushes, glosses and even brushes (only ~$50).... And it's convenient to carry around....
A friend got something similar from sephora last year and really liked the shades. I was actually thinking of getting it for myself just for fun :D
Rather than clothes or perfume,which are things that get used up and thrown out, how about stuff that she will cherish forever like jewellery (nice bracelet or earrings)...