The correct statement is:
They have the same speed but different velocities.
This is because Matt and Jaime both walk at 1.25 miles per hour, which is the same speed, but they are moving in different directions (east and south), which means their velocities are different. Velocity not only includes speed but also direction of motion.