After searching other gaming forums (none of them as good as this site) I found two threads of people complaining about this issue, and the one thing they all had in common was that they all had an SSD as their primary drive, and the game installed on a secondary drive.
The suggested solution was to disable the Windows page file from your SSD and re-allocate it to a different drive. It sounds nuts, but I did it anyway:
I used the instructions from this Super User question. I moved the page file off my SSD and onto another drive (not the drive that GTA-V was installed to though).
And, hey presto. Game works great. I don't know why this would be an issue, as moving the page file off the SSD seems counter-intuitive, but it worked.