What about personal gifts? Gift cards, wine, etc.
Don't go there.
The only time it's OK to give gifts to subordinates is if all of your subordinates get essentially the same gift at the same time. Always always check with your legal officer on this first. There's a hard (and fairly low) $ limit.
Better options -
1) Submission for awards. Though be aware that there is a perception, at least partly rooted in reality, that a mid-tour award may reduce the odds of the person getting an end-of-tour award of higher rank. Anything you write up in the mid-tour award can't be used for the end-of-tour award. I've known people to ask that they NOT be nominated for an award mid-tour, just that they get bumped up to something better later. This is the Navy/USMC though, where awards are far from universal entitlements. I understand the Army and AF to be a little more free with handing them out.
2) Submission for quarterly local awards like (in the Navy) Sailor of the Quarter. These can be a little easier and faster to get through, and if they don't get selected then 3 months later you can try again. Selection usually comes with a 72 or 96 hour special liberty. As an aside, if you're a dept head, you should be submitting SOMEONE from your dept for these quarterly awards every quarter. It's a fair bit of work but the submission alone demonstrates to everyone that you care about, value, and appreciate their work.
3) Time off. Depending how high up you are in the food chain and where you are, you may have the authority to grant single days of special liberty. Be careful with this too though, because since there's no selection or review board involved it's easy to create the perception of favoritism when you single out people for this kind of reward.
4) If they're getting out soonish, tell them you'd be happy to write references for them, letters of recommendation, etc as they go job hunting or applying for school/training. This is something meaningful and personal you can do.