A recipe idea taken from the movie The Tao of Steve; it's mentioned offhand, as he's making it for his would-be flame. This is actually mahi mahi with mango sauce, but a marinade or even a different fish (lobster would probably be an excellent match) are quite feasible.

Anyway, so goes the recipe:

4 mangoes
1.5 cups of cream (half and half, or you can go for a full heart attack if you're up for it)
1.5 lb mahi mahi, fileted
1 tbsp cinnamon
sugar, to taste (depending on ripeness of mangoes)
lemon juice

Chop three of the mangoes coarsely; puree the remaining mango. Sautee the chopped mangoes in a skillet with butter until softened, then remove from heat. Add cream and stir a bit, scraping the bottom to get the remaining bits of sauteed mango into the sauce. Add cinnamon and the mango puree. Reduce to desired thickness, stirring constantly to make sauce smooth and thoroughly blend the cream and mangoes. Add salt and sugar to taste.

Prepare the mahi mahi by baking or broiling with butter, a dash of pepper, salt, and lemon juice. As noted above, a marinade is a good idea--simply mix or blend pureed mango and cream to make a marinade. As a cautionary note, too much mango (or too lengthy a marinade) will cause the fish to fall apart due to citric acid.

Serve the mahi mahi topped with the sauteed mangoes and the sauce. As a side, I recommend a salad with a raspberry vinaigrette.