USO Lounges at major airports. Love those fine people. Still use them and donate heavily after all the hours I spent stranded with them during active duty years.
The Metro NYC USO - great website with info on discounts and freebies.
http://www.usonyc.org
AMTRAK military fares.
Military MWR rec sites, such as Shades of Green hotel in the park at Disneyworld, Hale Koa Hotel on Waikiki Beach, vacation cabins/camping all kinds of places. Here's an example:
http://get.dodlodging.net/propertys/Solomons-Island
I have fond memories of the beach cabins at Barking Sands on Kauai, and the cabins in the volcano park on the Big Island.
And all the beachfront BOQs I have stayed at over the years!
At most military bases of any size, there will be a "tickets and tours" office, with discount tickets to amusement parks, movie theatre chains, event venues, inexpensive one-day bus tours to nearby attractions or cities. Some bases also offer rec equipment rental.
TSA pre-check airport security line. Follow directions at TSA.gov on how to enter your Known Traveler number in your airline frequent flier profiles if you are eligible.
Many retailers offer military discounts. Ask. Home Depot and Lowe's do 10%.