Which US territory/insular area should I see first, and why?
For the obsessives here, yes, I know that DC is also a territory in a sense, but I’ve been there dozens of times.
Go with the U.S. Virgin Islands or Puerto Rico. They are fairly easy to get to especially if you live in the South or on the East Coast. The U.S. Virgin Islands consists of three islands: St. Croix, St. Thomas, and St. John. They are fairly different from one another but each is your standard Caribbean paradise first and foremost. It is a great vacation place in general.
I don’t know as much about Puerto Rico. It has a very different history than the USVI but they are all fairly close together so you could see both on the same trip. Small planes run between San Juan and each of the USVI.
Where would you be starting from, robert? From most places in the “Lower 48” the shorter trip hourswise/the one with most alternative routings would appear be to the Caribbean islands.
Then it would depend on how much time you want to give the trip and if it would be possible to do a two-fer - spend a few days in PR then do the 20-30 minute hop over to the USVI. PR gives you the cultural contrast of a completely Latino society, an abundance of historic sites, a larger territory with wider diversity of ecosystems yet close access to a major metropolitan area’s resources, more varied types of lodging ; the USVI gives you an anglophone environment, more of the West-Indies “small-Island” cultural vibe (watch out for de traffic on de left, mon), and some fine island waters, plus the aforementioned free-port shopping. In the USVI if you go to St. Thomas then a daytrip or overnight to St. John via ferry is an attractive and affordable option; doing all three USVI is a bit more work. I place USVI as part 2 of the suggested “combo” journey because of the possibility of once there being tempted to do some free-port shopping and then it would be a safer bet to just pack and declare things once, checked all the way back to your point of origin.
BTW, if going to the Pacific, Guam and the NMI would IMO also be logical candidates for stretching it to a two-fer, given that you already have hauled yourself across all that stupefying breadth of ocean and they are also next-island neighbors (Guam, geographically, is the *Southern *Mariana Island).
I’d be starting from the Mid-Atlantic region. I’m less interested in raw travel time than suggestions based on how fun or interesting it would be to tour. I’m especially interested in an experience that isn’t just a tropical Jersey Shore with tacky tourist shops and crowded beaches.
Pacific Islanders or travelers, we’re awaiting any info from y’all. USVI veterans too, flesh out what little I provide, I’ve only traveled there very briefly on business.
As for the Caribbean (80% of the population and landmass of the Overseas Empire): The visitor has to apply some effort into avoiding the overtly touristy parts/activities and driving your rental car in the Islands can get, um, exciting. The crowded beaches part depends on whether you happen to hit them when the *locals *also think it’s a great time for beaches (e.g. SW Puerto Rico beaches during the week before and after Easter? Madness). But hard to not have fun in the Islands. There’s enough culture, nature, active-sport and nightlife attractions to keep one occupied.
Puerto Rico: Focus first on the San Juan historic zone (sorry but you’ll have to bear with the shops on your way to and from; OTOH fine dining if you are still there at night) and then move the heck away from the San Juan tourist strip to visit out-on-the-island places like the El Yunque National (Rain)Forest, Las Cabezas Nature Preserve in Fajardo (mangroves by day, bioluminescence by night! Near El Conquistador Resort, which adds golf and water sports), Ponce (Art Museum, Tibes precolumbian site, Hacienda Buena Vista), the Arecibo Radio Telescope site, the northwest coast surfing beaches (surfing, duh), or Vieques Island (uncrowded beaches, diving, more bioluminescence).
Prior Threads including Puerto Rico info about places away from the usual strip and links to yet other threads on the same subject:
http://boards.straightdope.com/sdmb/showthread.php?t=313243&highlight=Puerto+Rico
http://boards.straightdope.com/sdmb/showthread.php?t=295139&highlight=Puerto+Rico
USVI: In St. Thomas, various historic locations such as Ft. Christian, the Legislature House, the Synagogue; then ferry to St. John Island for a huge National Park Preserve where you can get away from the hurly-burly.
go to the midwest 
I’ve been to Puerto Rico, the USVI and to Guam. Really enjoyed St. Thomas, but that was back in 1976 and I was usually blitzed on rum and Coke when I wasn’t working. No idea what it’s like today, but probably touristified beyond measure. Really hated Guam, but then I’ve always hated heat and humidity and bugs. If you’re a scuba type, you’d probably like it. Puerto Rico didn’t impress me, but I didn’t see much of it.
Do not go to the US Virgin Islands, because there aren’t any there.
Instead, go to American Samoa.
Because of the old saying.
.
.
.
.
.
.
.
.
Samoa sa-merrier.
St. Croix is like a second home to me. It is the largest of the USVI and is not crowded at all. There are two large towns on the island but it is mainly goat pastures and rainforest besides that. There are some hotels and resorts but plenty of space in between. You can have picture perfect beaches to yourself if you want that or there are a few that have some people on them. It is NOT the Jersey Shore or even touristy like St. Thomas. St. John is even more secluded but most of it is a preserve.