How's about linking a pedometer function to an ability to speedup/slowdown music to match or be a multiple/factor of your running pace.
result: select any dance tracks/playlists, get running, phone adjusts bpm of tunes to fall into line with running pace, happy run!
Perhaps even add some functionality so that at certain times during the run the bpm could speed up by a few % in order to drag the runner into a burst of speed...?
Pete