Osu !
Pas mal d'anime correspondent à ta demande, mais pas forcément pour les mêmes raisons.
Un trio va voyager dans le Japon à la recherche d'un certain individu. C'est un classique donc tu l'as peut être déjà vu. Ils rentrent dans la catégorie vagabond parce qu'au final ils ont pas de thunes ni de GPS, donc ils ont plus l'air d'errer que de voyager avec un but. Dans la même veine je recommande Michiko to Hatchin, sauf que ça se passe au Brésil.
Globalement ce qui a inspiré Kino, sauf qu'ici on voyage dans l'espace. J'pense que le train de nuit dans la voie lactée de Miyazawa Kenji a inspiré/est référencé dans pas mal d'anime, donc ça peut être une bonne piste de recherche si ça te plait.
Dans le même genre avec un voyage dans l'espace et des aventures épisodiques tu peux tenter Space Dandy, Kaiba, Valerian et Laureline (en français) ou Yamato 2199 (qui a un but un peu plus clair même si l'objectif reste flou et les fait pas mal errer dans un environnement hostile).
- Tsubasa Reservoir Chronicle
Là j'recommanderais plus le manga, ici on voyage de dimensions en dimensions, et ça sert globalement de cross over entre les oeuvres des CLAMP (CCS, XXX Holic, Kobato, X etc etc...). Je sais pas trop ce que donne l'anime, mais dans l'idée tu retrouves le fait de découvrir de nouveaux endroits/de nouvelles sociétés et coutumes, comme dans Kino ou Ginga Tetsudou 999.
- Ayakashi (épisodes 9 à 11 seulement, arc Bakeneko) et surtout Mononoke
Ici on est vraiment proche de Mushishi dans le sens où on a un rapport au fantastique avec un apothicaire qui se déplace d'endroits en endroits et qui "aide à résoudre" des situations en lien au surnaturel. Par contre le parti pris graphique particulier et le côté huis clos des arcs fait que t'auras pas forcément l'impression que le héros vagabonde. Alors que dans Mushishi on a un focus sur les environnements et la nature.
Un voyage avec des "loups" à la recherche de quelque chose. C'est assez sombre, voire déprimant je dirais. Les OAV sont des must pour conclure le show d'ailleurs. Dans une vibe similaire tu peux tenter Ergo Proxy. C'est aussi ressemblant pour la réflexion qui est amenée derrière le voyage.
Enfin, deux trois trucs en vrac :
- Spice & Wolf. Pas vraiment vagabond, mais le héros est un marchand itinérant, et ça voyage pas mal.
- Monster. Ici le héros vagabonde pour échapper à la police. C'est un ancien docteur réputé accusé d'un crime. C'est un thriller autrement, et niveau ambiance c'est pas forcément loin de tes deux exemples, sauf qu'il n'y a pas de fantastique c'est à 100% ancré dans le réel.
- Trigun. La tête de Vash est mise à prix, ça suffit pour en faire un vagabond.
- Seirei no Moribito. C'est plus statique que je ne le pensais au départ, mais l'histoire d'une garde du corps et de son client qui "fuient" et se cachent pour leur vie.
Sinon j'pense que la plupart des shows taggés "aventure" et proposent un voyage ou un contenu épisodique te plairont. L'idée de vagabonder implique de ne pas avoir de but, mais parfois ton but est tellement flou que tu finis par énormément tâtonner. Un de mes VDD a cité One Piece, et une personne après moi pourrait te parler du Voyage de Chihiro et ça correspondrait à ta demande. Si tu veux quelque chose de plus ciblé et qu'un autre élément t'a plu dans tes deux exemples, identifie le et affine tes critères de recherche ^^