How can characters encounter “strange new worlds” etc. without resorting to a trope?
Obligatory: Tropes aren't good. Tropes aren't bad. Tropes are tropes.
You always travel at the speed of plot, because that's why the story exists. If you have a good story in mind and you need to use one such trope, then there's no shame in doing so. All you have to do is establish a set of rules and stick to it.
As far as we know, there's no way to travel vast distance in a timely fashion. So if you want to do that, you'll have to make a choice.
If you want to remain in the harder part of the SF spectrum,
I would advise to remain unspecific on how the technology works. If you simply state what it does without explaining the how, nobody can tell which laws you're breaking, so really from a certain point of view you aren't breaking any. Alternatively, you can make up one rule that allows FTL under certain conditions. Once again, you don't have to be specific, just consistent.
With that in mind, FTL is one option. That will allow you to have a planet-of-the-week type of adventure, meet new civilisations by the dozen, etc. Alternatively, wormholes, stargates or whatever else you can think of.
FTL by the way doesn't have to be instant, and it doesn't have to be convenient. Maybe you can only travel from and to specific points in space, which means reaching the damn points in the first place, which can be an adventure by itself.
Another option is to keep it only in one solar system, or one planet even.
Consider that on Earth there are many biomes, many cultures, and that you can't really explore it all in a lifetime. If you have a big planet, with big natural separations, you can realistically have widely different cultures, maybe even slightly different species, on a same planet.
If the story is really about meeting new people, all you really have to do is cross the street. You don't need FTL for that.
Another option is to keep it hard all the way (that's what she said - sorry, I had to) and travel at a fraction of c. That means it takes a relative long time to go to another planet. If you have a self-contained adventure on each planet, it doesn't really matter how much time passes.
However, the time difference can be used to add to the strangeness. Even places you know could be radically different. An example of that is The Forever War. Every time the characters come back to Earth from a mission, they essentially are at a different point in the future where everything is new and weird. That would qualify as strange new worlds.
Another option is alternate realities. Granted, instead on relying on speculative FTL it relies on speculative alternate realities. And you'll still need a thingy to do that. There's an episode of Stargate Atlantis where they find a ship that just jumps from reality to reality, and they all are different in some major way.
You can explore strange new worlds this way. It can be actual strange new worlds if the device is in a different location in each reality. It can be our own world where everything is just slightly off. You can explore differences in culture, and differences in one's life based on how events turn out.
Another option is VR. You don't actually go out there to meet new civilisation, explore new world. You just strap a VR helmet and think you do. So the story happens in your mind/in a video game.
Come to think of it, Assassin's Creed is science-fiction and all you do really is exploring a VR space that recreates a portion of history. If your character believes they're living an adventure, is it different from actually living the adventure?