According to the AC Characteristics table for the W65C816S, certain parameters are dependent on the frequency at which the chip is being run at, eg. tAH = 10ns at 14MHz, and 40ns at 2MHz. I understand that some parameters are obviously frequency dependent, such as Clock Pulse Width Low and High, but why do the Hold and Setup times of the chip change?

You're looking at the 1.8V spec.s. The part can work at 1.8V, but it was primarily intended for 5V; so when you cut the power supply voltage down to 1.8V, the internal propagation delays and transition times are slower.

Also, it looks like the original chips were 'binned' for speed -- some are rated for 2MHz tops, some for 4MHz, etc. As yields improved, quality became more consistent, and now they essentially only have one processor -- the 14MHz part. Which I guess is supposedly able to go as fast as 20MHz, but whether it's consistent is unknown to me.

Thanks for the explanations, I never considered the VDD row.