1 second of latitude is about 30 meters so maybe it's a rounding error in your calculation. Can you measure position more accurately? e.g. to 0.1seconds
IIRC, Haversine uses differences between coordinates.
If you calculate the full latitude and longitude as a floating point number from the GPS sentences, there probably aren't enough digits to accommodate small distances. You can try doing the subtraction before the conversions.
ie you get two longitudes from the GPS in forms like 37 degrees 42.12345 minutes and 37 degrees 42.12000 minutes. Converting to degrees you'd have 37.7020575 and 37.7020000, and the difference is off in digits that the floating point format doesn't preserve. Subtract first to get a difference of 0.00345, and you'd be in safer territory.
What are you using to get the latitude and longitude coordinates? What software libraries are you using, and where did you get them from? There might already be a function to calculate distance in one of the libraries you are using.
Please post your code.
Perhaps @eng76em is attempting to calculate a very small angle from its cosine, which of course will lead to trouble, because that cosine will be indistinguishable from 1. For a circle the size of the Earth, an angle corresponding to a distance of 1 km will have a cosine of 0.999999987... which is, at the Arduino's arithmetic level of precision (about 7 decimal digits), indistinguishable from 1.
Perhaps better to use a formula involving sines instead of cosines, in order to avoid such an error. Such a formula can be found here: