If you don't mind exploration being relayed as subgenre:
Shin Angyo Onshi - Story of a government inspector mandated by the king to punish corrupt officials. After the King's death, the MC wanders, carrying out his duty despite the country's fall
Heart Gear - a recent manga where the MC is raised by a robot after humans went extinct. She goes on a journey to look for humans in a world where only robots are left.
Samurai Champloo - MC on a journey to find someone
Samurai Deeper Kyo - don't remember much, but the MC was kind of a wandering pharmacist
12 kingdoms - an old isekai where the first parts has the MC escape pursuers in an unknown world. The story switch from being a fugitive though, so exploration subgenre disappears on the way
Dororo - A guy hunting demons to get back his body parts. The anime starts out with a bang but I dropped it when the animation quality plummeted.
Kiba no tabishounin The Arms Peddler - Weird ass wandering journey in the Western setting populated with High fantasy monsters, vampires and demon. The FMC is wandering to provide magic weapons to the people in need.
Mahou Tsukai Kurohime - Evilest, badass magician girl on a mission to "learn love" to lift her curse. She's trapped into her teenager self, and wanders the western high fantasy world to cure her condition.