The Story of the The 9th Roman Legion has become the stuff of legend. Recently three different movies have been made of the story each slightly different from each other, all worth a watching. The Last Legion (2007), The Centurion (2010), and The Eagle are all excellent fodder for an adventure story line, and damn good movies. I like The Eagle best for this purpose because it is most "quest-like".
Marcus Flavius Aquila and his Brigante slave turned companion Esca set off beyond "the edge of the world" North of Hadrian's Wall on a quest to find the lost golden eagle, standard of the 9th Legion. The 9th had explored the North and disappeared, never to be heard from again. Their standard represented the honor of Aquila's family, and so Marcus seeks to regain the eagle and restore his family's honor.
The movie is based on the book The Eagle of the Ninth by Rosemary Sutcliff (1954), which is a historical adventure novel designed for younger readers. I've never read the book, but it seems to be in the same league as The Book of the Lion by Michael Cadnum, another historical adventure novel, but set during the crusades during the reign of Richard the Lion-Hearted.
The movie, has a good adventure session feel to it. Without going into spoilers, several "encounter-like" scenes outline the quest for a small band of adventurers. The various tribes make for interesting and compelling foes along the way, but one could substitute other creatures easily if one wished. Wild eyed druids driving scythe-wheeled chariots, shamans drinking magic potions, wild boars, savage painted tribesmen with skull headdresses, tattooed rogue warriors, snarling war dogs, thiefly infiltration, betrayal and battles a-plenty make for a fully epic adventure.