The 2 codes have nothing to do with each other.
P0500 - Speed sensor - Likely a wiring issue, but sensors have been known to fail
P0138 - O2 sensor at the rear of the catalytic convertor is likely bad. This would explain some of the running issue you explained. Don't buy the cheapest sensor out there. This is one time the OEM part is a good idea.