Since I'm not overly thrilled with high magic racial powers, I gave some thought to a few options for very "high elf-ish" abilities to use as possible replacements for Fey Step. Here's my quick list:
1. Easiest - Reflavor "Fey Step" as an ability that just lets the Eladrin easily sprint across 25 feet of any terrain, including water, without incurring attacks of opportunity. This plays kinda like Legolas's ability to sprint across ropes, run on snow drifts and so forth. It's mechanically identical to Fey Step, but with different flavor.
2. Some kind of similar movement-enhancing ability, such as expeditious retreat, wild step or the like.
3. Some kind of fade into wilderness ability. Starts to blur the line between them and elves though.
4. Some basic utility enchantment, or possibly an ability that let them alter their appearance. That plays up the fey aspect of them a bit more.
I might take a look at the Eladrin entry in the Monster Manual for inspiration.