Setup Time & Hold Time - By popular demand

a) Generally speaking SETUP fixing is always DIFFICULT. This can be resolved by inserting buffers (as you mentioned) only in cases where
the SETUP violation is because of large load/slew violations which causes huge delays in combinatorial blocks. say there is an AND gate which is driving much more loads than it should and you see A to Y delay for that 3ns. Now this load violation can be fixed by adding a buffer after the AND gate and you may see now the AND gate has aonly 1.5ns and BUFFER added 0.3ns. Thus you gain 1.8ns in data path. To see if load/slew violations are causing your SETUP failure see report_timing with -cap -tran (assuming you annoate set_load or SPEF file also while doing STA). But if load/slew is NOT the culprit..then it is indeed tough to fix SETUP and you may need to revisit the logic structure between the flops.

b) HOLD fixing is comparatively far easy. Simply by adding buffers in the data path. There are lots of automated scripts and even DC can do that with -fix_hold. This is generally done at the last stage after the CLK routing has been done.

c) I would say both are equally IMPORTANT and any one of them is sufficient enough to cause a RESPIN :-(

Finally MOST important thing to remember always is SETUP is frequency dependent..while HOLD is NOT!

Note: This is generally true if you use only +ve edge clocking. If you mix both +ve and -ve edges in your design, then hold time also has a frequency dependency.