What piece of gear would you tell a first time deployer to make sure to have?

If the environment is suitable, a laptop with plenty of games and access to e-books.
If internet is available, an online learning plan to better yourself and make productive use of downtime.
A deck of cards and maybe some poker chips for when you're feeling social.
Some visual training aids for when you are not feeling social.
A last letter, just in case.
A small token from everyone important to you back home. For me, that was a picture of my family all together, another of just my wife, a small square of fabric from my youngest's baby blanket, a bead bracelet my daughter made for me, and my middle son's teddy bear, which he insisted I needed more than he did even if he was afraid of the dark.

If in an austere environment,
A compass.
Signaling mirror/ strobe.
A quality multitool
100ft of 550 cord
A phrasebook in the language of the local inhabitants

The almighty woobie!

Baby Wipes

Compact folding camp chair.

A good camera to document your deployment and a good multi-tool always a great thing to have. The areas of deployment have flourished since the first years of the engagements so I believe the needs have changed. If they were the first boots on the ground in an austere environment, I would whole hardly recommend baby wipes and those type of things to help your cleanliness because there was no better feeling than to clean yourself up a little bit when your own smell became unbearable.

Multitool (they don't issue them anymore)

A USB stick or memory card with:

1. The Complete Works of Rudyard Kipling , most troops come to his way of thinking soon enough.

2. The Bible, most troops come to it sooner or later as well.

3. A last letter kept up to date for one's family. Address parts to your significant other and each child no matter their age now. Something for those who care for you or you care for. Forget perceived wrongs since they will no longer matter if this letter is ever needed.

4. Something to remind you from time to time that in life all men know fear at some point and that's OK as long as you can do your job. Being afraid and doing your job makes you a soldier. I doubt there was anyone on Omaha Beach who was not afraid yet they ll walked off those landing craft.

The below is from a guy named James Warner Bellah. Some of his short stories were turned into films by John Ford, including Fort Apache, She Wore a Yellow Ribbon, and Rio Grande. He too was a vet and between him, Kipling and the Bible I got thru OK. Most troops do.

"The fears of man are many. He fears the shadow of death and the closed doors of the future. He is afraid for his friends and for his sons and of the specter of tomorrow. All his life's journey he walks in the lonely corridors of his controlled fears, if he is a man. For only fools will strut, and only cowards dare cringe.' -- James Warner Bellah

Well since I deployed in 03/04 OIF 1 I'd say more dip and cigerettes, baby wipes, mini folding chair, and a pocket pussy

Socks.
I know it sounds old school but if you are on your feet a lot and your feet look like prunes, a fresh pair of socks is a godsend.

Depending on where you're deploying, id make sure to stock up on moisture wicking underarmour boxer briefs and toss out any form of cotton underwear.. (Any that retain sweat or water) Foot patrols, clearing buildings, raids, dismounted missions, or any mission in general that requires any amount of maneuver with moisture retaining under-draws is a GUARANTTEED chaffing nightmare! Underarmour saved me and my nether-regions from the chafed groin and maneuvering with the MISERY that is chafed cock and ball