Other options I’ve tried, being in much the same boat:
Big bus package tours of Europe. Fun. Easy. Meet tons of people from all over. Groups are too big. Stereotypical tourist experience. The age-limited ones like Contiki tend to be mostly singles. Non age-limited ones tend to be 50+ and lots of couples.
Small camping tours, like TrekAmerica or SunTrek. Small groups. Got to like camping. Almost all singles. Lots of Europeans. Cheap. Low-key.
I think the hostel thing is the best, but these are other options if you want a stable group for the whole trip. The main problem is that smetimes the stable group sucks, and you’d rather have the freedom to ditch them all. Plus hostel people are more interesting than tour people. Sorry, but true.