I lived in Puerto Rico up until two years ago, didn't do much diving,(I was in college when I got my OW and didn't have the money to keep it up),but plenty of snorkeling...
Culebra (small island part of PR to the east) is a beatiful small island with plenty of dive oppt. Try doing a search for Culebra Divers on the internet, I think they are the only dive operator on the island(in Culebra). On the main island of PR there are plenty of opperators.
Also on the east coast there is another small island called Palomino, which is a very popular divespot.
Visibility varies with rain runoff, in my experience there, it varied from 30ft (on a cloudy day with rain on the preceding day, at Cerro Gordo, north coast) to 100ft +(beautiful day at culebra).
Both palomino and Culebra are safe bets for good diving.
I have no experience in diving off Vieques, but it is so close to Culebra that it should be pretty similar. The local fishermen that I have spoken with tell me that the best areas are off limits because the US Navy uses them as practice range.