I did notice shortly after replacing a set of tires that the amount I was being shocked changed dramatically.

Right. Some tires have a high degree of conductivity, others do not. Depends on what compounds are in the rubber. It's quite common for a set of aftermarket tires to increase the amount of static shock you get on leaving the vehicle.

I've gone through a lot of trials and tribulations trying to get rid of the static problems in my car and don't have a solution except for the "be touching the metal of the car as you're getting out instead of touching it after you're already out".

Which, by the way, works because the soles of your shoes transmit the built-up static charge slowly over a large flat area (the soles of your feet) instead of quickly through the tiny point of your first touch with the car's metal upon exiting. The trick is that you have to be touching the metal when the soles of your shoes hit the ground.