My recommendations:
A good LED flashlight that is small and runs on common batteries. I bought a fantastic one at the Ft Bliss Px for $12. I wish I bought 10, as many others have shown envy and desire towards my flashlight.
Powder drink mix. This is available at the Px and DFAC, but they run out at times. Also, it is always the same Rasberry Ice flavor that I hate.
I brought a Dell Axim pocket PC and read ebooks on it. It has a backlit screen (I can read at night without bothering anyone else), and the charger works with 220VAC. A 1MB SD or CF card can carry hundred of books, plus pictures, music, even video clips. It fits in a standard GI first aid pouch. I got mine from the Dell Outlet. Sometimes they have special deals or coupons for new ones.
Packages from home are critical, as is any mail or anything to connect you with friends and family.
Eyewear. A good pair of ballistic sunglasses with a shape that protects from wind and dust. Wiley-X or similar.
A couple good knives. A good rescue type knife for cutting seatbelts that can clip into the little webbing points on a IBA vest. Maybe a nice k-bar or some sort of double edged dagger type knife. Oh - don't forget the multi-tool. Very handy for crab legs at the DFAC.
However - most of the above is available at the Px at the stateside deployment center. Or the Px in Kuwait. Or the Px in Iraq. Also the new issue goggles are pretty good. The issue boots are pretty good. Most of the issue gear is much better than 20 years ago.
I've seen footlockers full of brand new pistol magazines (I literally mean a large footlocker absolutely full of first quality brand new factory mags) that no one wants because they don't know what to do with the magazines they already have. This may not be typical, but most units rotating out dump ammo and magazines on their way out and the units that get stuck with them are pissed that they have to figure out where to put the stuff.
A lot depends on the assignment. If you are at a desk ina FOB, by all means bring the karaoke machine and lava lamp. If you are in a rifle squad in a line unit, forget all that crap.
Oh - real important - bring D-ring/karabiners for attaching stuff to your body. Or to attach your body to a hoist if need be. For hanging your helmet off your IBA while in a building the cheap ones work fine.
Lastly, many companies ship to APO addresses. The internet is available to all, even if intermittently.