The two most remote sites in the Navy are Diego Garcia and Alice Springs. I don't think they have aviators at Alice Springs, and you don't want to go there anyways, it is out in the middle of the Outback of Australia.
There is also Gitmo, I know a few people who have gone there on IA and thought it was pretty good. Like anywhere remote though, it is a bit boring but at Gitmo can be broken up by snorkeling (diving?), working out and drinking.
You can go anywhere as a Defense Attache but those are very uncommon (if not unheard of) for a first shore tour. And I think they will be taken up by FAO's now anyways that they are coming on-line.
You could always go USAF, Thule and Shemya are still operational.