except for in specific contexts where I'm used to it (e.g. soy sauce with sushi, olives, etc.).

I wonder if that's an angle to pursue? I mean, maybe you'll have an easier time with foods where strong saltiness is part of the point, than ones which will taste to you like "familiar foods but with way too much salt".

If you're okay with being pesco-vegetarian, then anchovies were the first example that came to my mind.

Or tinned fish in brine generally -- one of my default low-spoon meals is a salad made from a tin of tuna or salmon, a tin of beans, some chopped onion, salad leaves if I've got any, a bit of olive oil and a bit of vinegar.