I don't remember having lettuce or tomato slices with a Filet-O-Fish in the USA nor even back in the 70's in the UK. But my memory may be playing tricks on me. Still, I don't think I *want* lettuce and tomato with it. I think it is complete the way I've had it served, with a slice of American cheese and lots of tartar sauce. No fancy cheeses please, no special chopped-pickles-tartar sauce on it.
For myself, the F-O-F is fine for what it is. It isn't gourmet food. Sure, it was better years ago - but time marches on and nostalgic reminiscences are subject to the Law of Diminishing Returns. It is not eGullet-oh-so-special food. Just eat it. Well, I do - and like it - and would always willingly eat one and seek it out when I am in the mood.
