evander13,
500 miles is about enough to get rid of the mold release and all that gunk in making a tire.
I'll bet the "squishy" feeling is because the tires are new and the tread blocks are much higher than your old, worn down tires. Heck, even a bowling ball would feel squishy compared to worn out tires.
Give it a few more miles and I'm sure you'll get used to it.