Check out the Blink spell for reference.
3rd level spell. Duration 1 minute (so basically a combat). At the end of your turn you have a 50% chance to disappear. You reappear at the start of your next turn within 10 feet of your original position (to a space you can see).
Now that spell pretty much makes you untarget-able about half the time. Which seems like its primary function. It’s a big effect. Very big. The movement is a minor component. And unless the movement would also make you functionally untargetable, it’s not anywhere close to the same effect.
IMO, you could easily have a mess of extra movement (on par with anyone else who has extra movement) at about the same rate. That makes me think of Expeditious Retreat. That’s a 1st level spell that lasts 10 minutes and grants you a bonus action dash, every turn for the duration (requires concentration).
So here’s my proposal. A spell like Expeditious retreat that permits a bonus action teleport up to 15 feet (destination within line of sight), concentration up to 10 min. OR a similar type of spell but instead of a bonus action, it’s your movement. So you’d gain a movement speed of Teleportation: 30 ft for the duration. Still needs line of sight and concentration.
That spell could easily fit on the Fighter’s spell list for level one spells and have a mess of utility throughout their career.
IMO that’s the smallest possible change you can make to get closest to the effect you want. No subclass, no class, no class feature shenanigans. One spell that’s mostly like another spell. I think you could put it on the wizard spell list too, so you can grab it as a feat.