I hope you are soaking the cod over night if it is really salted salt cod. Usually 12-14 hours changing the water a few times with the last soak being milk.
I've always thought the best way to prepare is a braise but if you can't have tomatoes then a "white" braise might do. Onions, garlic, peas, carrots, white wine, fish stock, etc.
Maybe throw in some chorizo and serve over rice. You could add some potatoes as well and serve with some crusty bread to soak up the braising liquid instead of rice.
It also works well for empanadas, and even frying it Milanese served with roasted red peppers in escabeche. Buñuelos or croquettes are also good but require more work. Yes on the brandade as well.
What I've noticed about de-salted salt cod is that it's more mealy. Not as flakey as fresh.
I'm already hungry. . .