I'd go for Guam, if I remember correct, there is a nice Westin or Sheraton there...
-I'd also take the Islander Hopper in one direction (both is alot). It's one those things you have to do like once in your life... (kinda like the Concord would've be...). Esp since who knows how much longer they'll keep is going (hopefully a long time as this is a very economy vital flight)...
-Vincent