I run with an iPhone in a running belt, a BT HR monitor (Wahoo TICKR Run), and the Magellan Echo. I'm very pleased with the setup.

The Echo is now compatible with several Android phones as well. Given your description, I think you'd really like it.