If you want lots of teleportation, Horizon Walker is the gold standard, but it doesn't come online until level 11, which is halfway through the game.
i would not call level 11 halfway through the game. Most campaigns never go over level 7. And only a really small percentage go over level 11. So level 11 is more like "endgame".
Also even from the experience, apart from the really fast levels 1 and 2, levels 3-7 (or 9?) take quite a bit longer than levels afterwards.
Even with 5.24 which has level 3 as recommended starting level level 11 will be rare.
While at a mid to high level that would mostly do the thing, at low level it would not at all do the thing, which makes it not particularly appealing.
Which level explicitly do you have in mind?
I ask because I just looked some 4e stuff up. When you are a hybrid assassin (shadow) Warlock (binder) you can take on level 1 the hybrid talent feat gor shadow step then you have
- with shadow step at will 3 square (4/5 at 11/21) teleport as a move action, but must teleport from next to a creature to next to a creature.
- Shadow Warp this this does "slide 3" not teleport but from the name and flavour its really close (i mean you move in your shadow or let ab enemy move in its shadow) whenever you kill a target or a target next to you dies.
- As the assassin at will you could take "ninja to rush" an attack which can be used for charging with a shortsword (light blade) and automatically grants combat advantage if you jumped, fell or were flying this turn.
- As Race I would take pixie for the flying part it also has perfect stats with dex and cha. (Eladrin would give int + dex (or cha) and another once per encounter teleport but I think flying is better for your goal)
- As character theme you could choose spellscared harbringer. This lets you teleport an additional 2 squares once per encounter as a minor action (so this + shadowstep gives 5 square teleport)
This is on level 1.
On level 2 you can take a teleport 3 encounter utility from warlock.
On level 3 an encounter power from assassin which teleports 5 squares and lets you attack
At level 4 you could get with sorcerer multiclass "teleporting strike" whighketw you from range attack a target and then teleport next to it and attack it with a weapon
Alternatively you could get a familiar with 1 feat (as an arcane class) and with a 2nd feat get a teleport when you set your familiar to active. (2 feats can also be taken later level 6 and 8)
On level 5 a warlock daily letting you teleport and deal area damage qround where you go fron and where you go to.
At level 6 a reaction from assassin which teleports and makes invisible.
Level 7,9,10 etc. There sre also some teleport powers.
So there is a lot of potential teleporting going on.