Yes, you should use a RS232 to TTL level shifter. RS232 can go as high as +/-12V which would be bad for an Arduino input.
As an experiment you turn on the (undocumented?) data inversion feature in SoftwareSerial:
SoftwareSerial GarminSerial = SoftwareSerial(rxPin, txPin, true);