Jaymi,
Having been to both French Polynesia and Fiji in the last two years I can say: how much can you afford?
I know that sounds crass but seriously they're very different price-wise. My fiancé and I spent 10 days in FP June 2003. We stayed four nights on Moorea (over water bungalow at the Moorea Pearl) and had three two-tank dive days while there. We stayed five nights at the Kia Ora (garden bungalow) and had four two-tank dive days. Total, including airfare from LAX, all meals and one black pearl: $10K
Last summer (July 2004) we stayed 18 days in Fiji, nine nights on Kadavu and seven nights Malolo Lai Lai. We dove probably 12 days while there, mostly three-tank dive days. Total, including airfare from LAX, all meals and a few souvenirs: $10K.
As you can see, Fiji is WAY less expensive. On the other hand we're returning to French Polynesia this June for our honeymoon because FP is that much prettier. Seriously, I've never seen anything as beautiful anywhere else in the world. I'm not even gonna tell you how much the honeymoon is gonna set me back :11:
Diving wise I'd say Fiji kicks the crap outta FP, even with all the shark action. For me personally the sharks got kinda boring, I'm much more into the macro life like Fiji has. And the coral in a lot of FP is damaged somewhat, while Fiji (especially around Kadavu) was spectacular.
Your choice, in the end you can't go wrong with either...
-globetrotter