One of my favorite meals is a West African dish that consists of grilled whole fish, a couscous-like grain made of casava (just use couscous), and a "sauce" made of raw chopped peppers, onions and tomatoes, lightly and simply seasoned.
I also really love a mayo-free potato salad with fish - boiled potatoes, some chopped onion, olives, olive oil and vinegar/lemon.