How many nights will you be spending in Europe, not counting the night on the plane going over? That would definitely affect my decision. (I'm guessing it may be only a week.)
How fragile is your father? My first thought was total agreement with jazz+travels, but Holy Week (Semana Santa) is a zoo in many of the cities of southern Spain. The streets in Seville are massively crowded, for example. It often takes a lot longer than usual to walk from place to place, and substantial detours can be required. I get a sense from your post that these might not be good conditions for your father. After two years of no processions, etc., I assume Semana Santa will be an even bigger deal than usual in 2022. If your trip will primarily fall after Easter rather than before, this issue would evaporate. In that case, I'd again agree with jazz+travels and suggest substituting Granada for Malaga if your father can be on his feet long enough (hours) to enjoy the Alhambra in conditions that will almost certainly be quite crowded. If the Alhambra is a no-go for physical reasons, Malaga is probably a better idea. Granada is also hilly, which might be a second negative factor.
I would not do the Basque Country in April. It is a great area to visit in the summer, when it is usually considerable cooler than the rest of Spain. In April, cooler isn't necessarily a good thing, given that the area is also wet (rain about 1 out of every 2 days). If you're good with inclement weather (maybe upper-40s/low-50s and rain), this could be a good choice, though. One thing: The trip between Bilbao and San Sebastian is a lot faster by bus than by train, and I remember the train as having unpadded plastic seats (I could be mis-remembering). The train runs through some very pretty scenery, though.
Vigo is a big NO from me in that it ranks about last of the many dozens of Spanish cities and towns I've been to. It is not bad; it is just dull. There are too many fabulous places in Spain (and Portugal) to settle for dull. In addition, Galicia's weather is rather like that of the Basque Country--cool and wet, and thus not great in April.
If you decide your father may not be physically up to dealing with Semana Santa conditions and think my conditions about the other two options discussed above are valid, that leaves Route C and Route E. Unless you guys are big art fans (that would certainly make Madrid a top choice), I'd choose Barcelona and Girona. I love both and think you can spend two days wandering around Girona at a measured pace. And of course there's no problem filling a lot of time in Barcelona.
Madrid-Zaragoza-Barcelona would work, too, with just enough time in Madrid to do what you want to do there.
If not for guessing your father may not do well walking up and down a lot of hills, I'd suggest Madrid-Toledo or Madrid-Toledo-one other place (Segovia, Cuenca, Salamanca). But Toledo is very hilly, as is Cuenca.
I'm wondering whether a concern about hills is behind the omission of Lisbon from your potential destinations.