I like the idea of both the Cursed Reincarnation-story and the Water World-ish setting.
On what to choose... hm. Cursed Reincarnation is something I really like as a story, but it can require a lot of preparation and detail to get right. You say that your Water World-ish-setting has been written in some detail, so whichever you feel more prepared for.
One way to have the Cursed Reincarnation-story be all *extra spicy and interesting*, is to have to had the sacrifices have been given immortal lives to fulfill some task, and that through the millennia, they might have forgotten their original goal, and that they must rediscover themselves in order to reach closure for their cursed state?