Grind the cumin, coriander, chiles, paprika, herbes de Provence, peppercorns, and salt to a powder in a spice grinder or small food processor. Add the garlic, the juice of half a lemon, and a tablespoon of olive oil and grind to a paste.
Slice the tomatoes and mix with 1/3 of the spice paste, the juice of half a lemon, a tablespoon of olive oil, and 1/4 cup of parsley in a bowl. Marinate for thirty minutes.
Roast the pepper directly over a gas flame or under a broiler until the skin it thoroughly blackened. Allow to steam in a closed paper bag until cool. Rub off the skin, remove the seeds and ribs, and cut into small slices
Preheat an oven to 450° F. Peel and thinly slice the potato and onion. Mix with the roasted pepper, 1/3 of the spice paste, and two tablespoons of olive oil and spread over the bottom of a Dutch oven or heavy pot. Cook uncovered in the oven for fifteen minutes.
Remove the pot from the oven. Cover the vegetables with the fish steaks in a single layer. Spread the remaining paste over the fish. Spread the tomatoes on top, along with any liquid in the bowl. Peel and thinly slice the remaining lemon and spread over the tomatoes. Pit and slice the olives and scatter over the dish with the remaining parsley. Add 1/4 cup of water, cover, and cook for thirty minutes or until the fish is done.