My first reaction was “NW from BCN? How in heaven do you do that? You can only go N or S, and to go W you have to go S!” Then I realized we were just having a language issue, as well as a problem with knowledge of Spanish roads and railroads.
It’s west of BCN. Really. The map just doesn’t have the lines right
And nobody here speaks in cardinal directions. We refer to going south as “going down”… unless it takes you to a higher place, in which case it becomes “going up” 
From BCN to Lisbon, you can go about 20 different ways - what do you want to see?
You don’t say whether you’re going by car or public transportation. I’ll assume car, but you can get the same routes by train or bus.
Route 1: One day or two in Barcelona (take advantage of the Tourist Bus, it goes to all the important monuments and you can take and leave it as many times as you want to), then head S to Tarragona, W to Lleida, W to Zaragoza (visit El Pilar and sleep over), W to Logroño, N to Bilbao (sleep, visit Guggenheim), back S to Logroño, S to Burgos (visit the Cathedral, sleep), continue W to Leon (Cathedral, Romanic art, sleep), head W into Portugal to Braga and Porto, then S to Lisbon. If you’re going by train you may want to skip Zaragoza, although the food is different there than in the other parts.
Route 2: Barcelona, Tarragona, Zaragoza, Logroño, Burgos, then go on S toward Madrid but don’t enter it, hit Segovia and/or Toledo if you can (the Alcázares are two of the most beautiful castles in the country and Segovia’s cochinillo can make any vegetarian reconsider), then go on W to Lisbon.
The Algarve route sounds just way too long for what’s to see, you’re talking about going the whole way around! Unless you can get a ticket for the Alhambra in Granada (the only castle that’s more beautiful than the two Alcázares, and the view is just incredible), which you need to reserve in advance, I don’t think it’s worth it.
You may want to take a look at the UN’s list of World Heritage Sites. Spain has the biggest amount. It may be a good way to figure out what do you want to see.
You do not need to visit Jerez to get good sherry or Porto for good port. They’re both sold all over the place.
Ask your hotel receptionist for tips on restaurants. Explain that you would like to try local food - not Italian, Mexican, Chinese or Nouvelle Cuisine (aka tiny portions, large dishes, huge bills). Many bars and restaurants offer daily menus at reasonable prices (2 dishes, wine, water, bread, dessert, coffee and sometimes salad): they can also be a good way to check out the local food, although sometimes they can be very generic (90% of them seem to include spaghetti).
Don’t ask for paella. Foreigners always ask for paella. Just don’t, unless it’s in one of those daily-menu places or you go through Valencia.
If you go via Zaragoza, my own hometown (Tudela) is halfway between Zaragoza and Logroño. There are some superb restaurants, although the ones in hotels tend to be the tiny portion etc etc kind. Restaurant Txoko, in the Plaza de los Fueros, has a country-wide reputation as a top place - superb menestra (veggie casserole). Hotel Morase, on Paseo Invierno, is also good for veggies. This area claims to have the best veggies in the world - it’s hard to be perfect, but hey we try 
The restaurants on Plaza del Pilar in Zaragoza have very good daily menus, with local dishes as well as the usual spaghetti and salads. Burgos, León and Segovia are great for roasts. The best dried ham (jaMON seRRAno) in the world is from Teruel, you can get some in Zaragoza. Barcelona has restaurants for pretty much any kind of cuisine in the world, including many that specialize in the different Spanish regions.
And sorry this got so long. I’ll make sure my email is public - please email me with any questions, I don’t want to bore people any more!