I hate to sound like a broken record, but I really love fish tacos (Mahi-Mahi is the best in my opinion):
- 1 fish (or more if they're small)
- Lime
- Olive Oil
- Chili Powder
- Cumin
- Salsas, guacamole, chilies, cabbage salad, etc. for topping
Squeeze some lime on the fish, and rub down with chili powder and cumin (if you use American Chili Powder, you don't need extra cumin, but I would recommend real chili powder). Massage in oil.
Let stand for a few minutes, up to a few hours.
Toss skin side down on foil over a hot grill, and cook until the flesh separates when poked.
Serve immediately with any salads you like.
Edit:
You could also smoke it.
Brine before hand for a day or so in a simple brine with sugar and salt, spices at your digressions. Remove from brine and let sit, uncovered, in the fridge for 12-24 hours (allows protein to come to the surface and dry, which will later attract smoke). Smoke.
Good Eats had a few episodes on smoking showing how to make a home smoker for a few bucks out of various things (a box, a gym locker, an ammo box and a large clay pot in different episodes).