I have not seen Huesca. I spent 3 nights in Zaragoza last year, taking 2 day trips, and enjoyed the 4 hours or so I spent walking around the city. (I also spent 10 nights in Barcelona and 3 in Girona.) Zaragoza could have used some more time, I know. Its old town is attractive and seemed very lively; I was surprised at how many English-speaking tourists had found their way there. Zaragoza has an interesting restored Moorish palace as well. The bus/train station is in a rather isolated location with not much in the way of food options within convenient walking distance, so I urge you not to stay in that area if eating near your hotel figures in your plans.
Since you like smaller cities: There are two nice side-trips from Zaragoza. One of the most visually interesting towns I've visited is Teruel, with Mudejar towers as well as some nice early-20th-century architecture. But it means a lot of time on the train for a day-trip. The positive by-product of that is that few non-Spanish tourists find their way there.
The smaller town of Tarazona is also nice, and closer to Zaragoza.
I can't resist mentioning two smallish cities I like that are practical day-trips from Madrid. Toledo is of course #1, but Segovia and Cuenca are also possible. I liked both of them more than Zaragoza. Cuenca is viable only via the AVE train, and the prices of those tickets escalate rapidly after initially going on sale at bargain prices, so it's not economically smart as a last-minute trip.
Not in the same category as Segovia and Cuenca but also nice is the handsome old university town of Alcala de Henares, reachable by local train from Madrid.
One interesting (to me) point is that Cuenca and the aforementioned Teruel are rather close together. Alas, it seems there's only one bus a day on that route, which would make me nervous. And the bus takes 3 hours, so this would work better with a rental car.
I haven't seen Tarragona; my impression is that the Roman ruins are the main reason to go. I love Girona and think it's the sort of place that would appeal to you. It's worth visiting just for the large medieval district, but it has a number of good sights: a walkable wall, two cathedrals and a fine museum. Totally worth an overnight or two though there's fast train service from Barcelona. I preferred Girona to Zaragoza.
This Camino-de-Santiago-related website has a thread discussing bus service to San Juan de la Peña. I didn't follow the links, but it appears that any service may run only in high season. Having run afoul of a similar situation last year when I tried to visit the Picos de Europa, I suggest you not try this. You might go to Jaca for nought.
