I would say that XIII was the only game I felt lacked in sidequests of those I have played. Having said that, I've not gone far into most of the earlier FF's, so I'm not sure on them entirely. But VII, VIII, X, XI and XII had enough. I'm not sure on the full extent of XII's, admittedly, as I never finished the game (forgot the plot while doing sidequests... eh heh).

I agree that sidequests are getting too closely associated with battles nowadays.