Yeah, it's tough, especially if you exclude fish and seafood. About all I can say is that my wife found plenty to eat, just not always "traditional" dishes. There are some soups that are vegetable based, caldo verde comes to mind, maybe a bean soup, and of course any place likely will have salads, and if lucky, grilled veggies. There are some pickled vegetables, carrots mainly, and some restaurants serve a variety of rice dishes, including vegetarian ones. Migas are vegetarian in nature, but are usually served with meat as a side, so you might be able to ask for that separately. I think most restaurants try to list at least a few vegetarian dishes. If nothing else, Pastel de Nata are vegetarian.
Not sure how long you will be there, but most traditional restaurants serve a core group of dishes, your husband may tick through the main ones quickly, so nothing wrong with mixing in some Italian, or pizza, or other cuisines to mix things up.