Not so cool as the GYMP3, since you'll have to monitor your own heart rate (though asking the shoes to communicate with your heartrate monitor shouldn't be out of the question), but possibly more portable. Add a set of wireless headphones and a transmitter, and you've eliminated the embarrasment of the Antiphonal Running Shoes.

As a bonus, downloadable sets of exercise music slanted to particular tastes could be made available to users -- just plug your shoes into your PC/Mac and go. Alternatively, you could program your own selections.