How fast you need to go unsurprisingly depends on quickly you need to get there. I've estimated that 100kly is larger than the distance to most places within the Milky Way.

• Travelling at 99%c, you can cover that in ~100,000 years.
• Travelling at 50%c, you can cover that in 200,000 years.
• Travelling at 10%c, you can cover that distance in 1,000,000 years.
• Travelling at 1%c, you can cover that distance in 10,000,000 years.

Recall that there are at least tens of millions of stars in the Milky Way. There are probably many stars within 50kly or even 25kly of Earth.

Nonetheless, these distances mean that even at extremely fast speeds it would still take tens of thousands of years to millions of years. This may or may not be a problem. The universe will probably last for at least another few billion years, compared to which a million years is not much at all. The question is whether your expedition can survive that long between stars. (It might make a big difference whether you are sending only digital machines or humans too.)

What are the distances?

Taking stats from its Wikipedia entry, the Milky Way has a diameter of 150-200 kly (kilolightyears), however:

The disk of stars in the Milky Way does not have a sharp edge beyond which there are no stars. Rather, the concentration of stars decreases with distance from the center of the Milky Way. For reasons that are not understood, beyond a radius of roughly 40,000 ly (13 kpc) from the center, the number of stars per cubic parsec drops much faster with radius.[68] - Wikipedia

However, I will assume that the upper bound given of 200kly captures most of the 100-400 billion stars.

Our sun is 26.4 ± 1.0 kly from the Galactic Center (see image). It might be difficult to travel through the center of the galaxy, but let's assume that the distance you travel to get anywhere in Milk Way from our sun is no more than traveling to the Galactic Center (~25ky) plus the upper bound of the radius (~100kly), so approximately 125kly. That's the distance to the outer edge so actually the vast majority of destinations should be less than that. One could do some fancier trigonometry to get exact numbers and nice averages, but this gives us the order of magnitude: ~100kly to travel almost anywhere in the Milky Way.

That is probably still well above average since the density of stars is much higher towards the core. Likely there are a lot of stars within 50kly.