Vieques is amazing.
Bioluminescent bay is a must. You have to do it. No question.

The Navy base got turned over to the Dept of the interior last May so there are a lot of beaches open that havent been open in years. Rent a 4wd (jeep, tracker, etc.) as a lot of the best beaches are down dirt roads. Theyre not bad roads, but they can be a little bumpy.

If Blue Caribe divers in Esperanza is still open (it was for sale last I checked) take their snorkeling tour out to Blue Tang Reef. Beutiful snorkeling spot.

This site has lots of info:
http://www.enchanted-isle.com/vieques/

And heres a bunch of my photos from when I went there.
http://www.bigblackvan.com/vieques/
the username is: zachs
the password is: photos

Jwtadmin a close friend of mine, and a member here on the board just went there last spring so if he feels like piping up, or if you want to PM him, I'm suree he would probably have a lot of good info as well.