If you have never been to NYC, you should go.

Places I have been as an adult:
San Francisco
Las Vegas
Honolulu

Places I have been as a child/teenager:
Honolulu
Los Angeles
Denver
San Diego
Tecate, Mexico
Paris, France

How long of a trip are you talking? Is renting a car or buying a train ticket and traveling around a little bit an option? If I were in your shoes, I'd probably swing for the Philly/NYC/Boston area or the Portland/Seattle/Vancouver thing (although the former would probably be more different than the latter, so more the better). Or possibly Toronto/Montreal.

For comparison's sake -- I've lived all my 28 years in Oklahoma and Texas.

As a child, my travel limits were basically Branson, Missouri, Springfield Arkansas, a few trips to Dallas, and one trip to San Antonio/Corpus Christie.

As an adult, well:
Colorado (a few times, but mostly mountain/rural areas)
Chicago
Florida (all over the state, mainly Orlando, Miami-ish/the Panhandle)
San Francisco
Portland/Seattle/Vancouver/Victoria Island
Southern France
London/Newcastle/Glasgow/Edinburgh/Cardiff
Rome
Reynosa/Monterrey Mexico
San Pedro Sula/Copan/Roatan (Bay Island) Honduras

As you can see, you can draw a straight line between Chicago and, say, Miami, and I've not visited anywhere in North America beyond the NE of that line. It bugs me.

YMMV.

Alaska!!! Mid September is a great time to see the Kenai and Denali! Your mind will be blown by the beauty of the place. Go fishing for Coho!

um, isn't rhapsodie in AK?

If it were me, I would immediately say ... Alaska. But since you are from Alaska, that probably wouldn't work for you. Hey.

I don't know your history, but if you have lived in Alaska your entire life, then you may want to try somewhere that is the polar opposite of what you're around on a day-to-day basis. For instance -- the southwestern desert.

In southern Utah, northern Arizona there are a series of national parks and monuments that are absolutely stunning in their beauty, yet about as far from the Alaska experience as you can get. You may wish to consider flying to Salt Lake City, renting a car, then spending a week visiting:

Arches National Park
Canyonlands National Park
Zion National Park
Bryce Canyon National Park
Grand Canyon National Park
Cedar Breaks National Monument
Capital Reef National Park

DAMN!

I guess you've already thought of going to Alaska, then. :P

Wow, Alaska to Hawaii is more than 10,000 miles? How is that possible?

If it's any consolation, AV, you may have talked me into going to Alaska.

Alaska's boring ; )

If it were me (and if limited to where Alaska Airlines flies), I'd choose San Francisco, Portland, or Seattle. You've been to San Francisco; most Alaskans I've known have liked Portland better than Seattle (to move to, anyway). There's plenty to do in the Seattle area if you have a car, but if not, you may find Portland more mellow and less touristy than downtown Seattle. You need to get yourself to Powell's Books someday.

Can you really use those miles to fly on another carrier to places eastward?

Also seconding netbros recommendation of southern Utah / northern Arizona if you can do the road trip thing. I did that driving from Seattle last summer; make sure you have decent air conditioning or you will shrivel-up and die.

ufez: Car? Train? Ferry? I'm open for just about anything. And I'm thinking 4-7 days; nothing big, but since travel from Alaska takes so long, it has to be longer than a weekend. I'll be on the NJ shore the first of June, and we will be spending a day or two in Philly, but not long enough to get to NYC.

AV: Yes, I am so over Alaska. Hee. But don't even try to convince me to move. I've been here my entire life, and from what I've experienced of other places (albeit not much), I'm not in a big hurry to leave.

netbros: The only dessert I've experienced is the tundra. That sounds like a fun option!

Eideteker: Because Alaska to Hawaii is so popular (extremely so in January and February, go figure), they are more likely to fill the seats with full-paying customers. So they "charge" 30,000 miles for a round trip mileage ticket. But Alaska Airlines just started going to Kona and has a $300 each way special for this December that my partner and I might jump on. We could sleep on the beach, if necessary.

box: Come to Alaska! I have a couch! Access to boats and fishing supplies and Secret Spots!

D.C.: I can use the miles on Alaska Airlines partner carriers, but the miles don't go as far. It takes 30,000 miles for a round-trip, say, instead of 20,000, and I don't have any extra miles to throw into the trip. As for Portland, I know most of my high school graduating class went there for college, but what's there?

D.C. is right about the air conditioning for southern Utah in mid-September. It is still pretty hot in the desert, especially for someone used to the other extreme in Alaska. Should you decide this is something you might be interested in, you may want to wait one more month until mid-October when the temps are very moderate and considerably more pleasant.

Arrgh. 1 "mile" should be equal to 1 actual mile. Otherwise, call them something else. GAH.

They are called such because you earn one mile for every mile you fly. It's like the Rent 10 Movies Get Your 11th Free deals at the movie stores, only it's Fly 20,000 Miles And Get Your Next Ticket Free (unless it's a popular destination then it's 30,000, or maybe 50,000 depending on our mood).

Seconding the Arizona option, if you can do it. I've camped in the desert around Phoenix (particularly the Superstition Mountains) a few times, and it's an incredible experience. It's true that October might be better for that, though. (I've usually gone in April.)

Washington, DC or NYC or the desert (northern Arizona gets my vote).

Although I grew up in Alaska, I love the Southwest and did many road trips through there as a child. I'll never forget, though, the summer I was eight and we did the trip in my grandmother's cramped Subaru with NO air conditioning. Days of hellish driving. I got mild heat stroke and vomited in Death Valley.

If you have a good rental car and enough time it's definitely worth it.

Portland's nice if you want to hang out, go to shows, restaurants, etc. Of course, it's easier to do that in a non-touristy way if you have friends that still live there (which is always part of the fun). Plus Powell's, dammit. I'd take a day in Portland over Seattle anytime. Perhaps with this free trip you'd prefer something more exotic. You could also fly to Seattle, spend a day or two there, and then take the train south.

If you came to Juneau I could probably find one of those disposable Princess Tours rain ponchos and you could mingle with the cruise ship passengers.

I have done more than enough mingling with Alaskan cruise tourists during my time working for the ferry office, thankyouverymuch. I could take my miles and fly to Barrow! Or... Fairbanks!

I hadn't even considered the Arizonan desert before this thread. I think that and NYC are probably both as different as you can get from Alaska. I'll bring them up with my brother and get his thoughts, though I'm betting he'd lean more towards NYC. Thank you all for the great suggestions, everyone!