I was in the Navy from 69 to 73, and I'd like to suggest Norfolk, VA, but I understand it's been improved since I was there. But of all the places I visited overseas in my Navy days, it's probably a toss-up between Naples, Italy and Montego Bay, Jamaica.

Wait, I forgot Izmir, Turkey.