There are a couple of ways to produce hypervelocity stars. A common one involves an interaction between a supermassive black hole and a binary system, leading to one star being ejected at speeds potentially exceeding 1000 km/s. I believe the current record is held by S5-HVS1, which appears to have been ejected from the Galactic center at a speed of $\sim1800$ km/s (Koposov et al. 2019). Assuming that the star doesn't slow down significantly, it could reach a distance of about 100,000 light-years (roughly corresponding to the edge of the Milky Way's disk) in about 17 million years. Not bad!
This isn't ideal for your scenario, though, since you want to remove the Sun from the galaxy, and we're about 25,000 light-years from our central supermassive black hole, Sgr A*. It would take an extremely improbably sequence of events to send the Solar System to the Galactic center and have it undergo encounters with multiple bodies in order to be properly ejected. So we might want to look elsewhere.
Another scenario would be to have the Sun, when newly-born, be bound to a companion star which subsequently goes supernova. The explosion would cause the system to become unbound and send the Sun moving away at speeds akin to classic hypervelocity stars. US 708 (Geier et al. 2015) was likely ejected in this manner, and has achieved a speed of $\sim1200$ km/s. If the same thing was to happen to the Sun, it could travel the remaining 75,000-ish light-years to the edge of the disk in roughly 19 million years. As supernova progenitors typically live for no more than millions or a couple tens of millions of years, the whole process could happen very quickly compared to the lifespan of the Sun and the time it would take life to subsequently evolve on Earth.
Would planets survive the explosion - and, furthermore, remain bound to the Sun? Well, we've found planets orbiting supernova remnants, so it's quite possible for a system to have planets after a supernova has taken place. That said, it's unlikely that this alternate-history Solar System would look the same as ours; I'm worried about the outer giant planets in particular. It seems quite possible that planets in tighter orbits, like Earth, could be retained, though - particularly if they formed in the wake of the supernova.
Another possibility, as noted by Adrian Colomitchi, is to utilize interactions with another galaxy, such as the future collision between the Milky Way and Andromeda. While most stars won't be ejected, some certainly will, accompanying the formation of features like tidal tails.