I do not have a 625M but 625XT myself and the 580P is better for cycling: Clearer screen, more fields speed/cadence etc.
HR band should be included with the package. The 580P uses an ANT+ band, similar to the major competitors (so it is different from the 625M).
The 580P is not the best match for running though, the GPS SW is optimized for bike "movement" so the pace is not presented well. If you keep the device in the pocket, the GPS coverage seem to suffer too.