Even without a gameboard, and even without finely tracking movement at all, you can still have players with movement builds and make them feel powerful. Describing opponents like longbow users and warmages as being within range of a move action "for you, but not for the others" is just one basic way to make them feel fast. Things like difficult terrain being an effective nonissue for them is good to keep in mind. Just remember to describe how fast they are in combat, and give them fun things to do with that speed.