After many tries, I finally was able to fine-tune my solo deck and defeat the infamous "Escape from Dol Guldur" scenario, with me choosing my prisoner (Theodred is the ideal candidate with this deck, of course).
Early game: Mulligan for Steward of Gondor / Unexpected Courage. If you can manage to stack Unexpected Courage + Dúnedain Warning on Aragorn, he'll defend for you, attack back, and make coffee for you on top of all that. ;) Add a Celebrian Stone and a Steward, and he'll manage the game almost by himself. Almost. Eowyn is of course the best quester nonetheless, and will bear Gandalf's Map whenever you're ready to engage stage 2b.
I added Beorn to be played in conjunction with Sneak Attack and/or Stand and Fight. Gléowine is also meant to be discarded by using Éowyn's ability, then brought into play with Stand and Fight. This and Valiant Sacrifice are the two ways to draw more cards, especially if your Gandalfs are much needed to counteract threat (which is exactly what happened in my winning playthrough).
EDIT: I'm aware that the deck isn't strictly speaking "progression" with 3x Dúnedain Warning from CatC, but the latter expansion was part of my initial purchase so I came to use it anyway. However, that card can easily be replaced with interesting options from the Core set, such as Hasty Stroke or Wandering Took (the latter if you need more allies).