Apple is still signing iOS 4.1 for the iPhone 3GS, so you could try that (if you don't have SHSH blobs for other versions of iOS).
Issues with 4.1:
* sometimes initiating a call will fail.
* poor app compatibility!
* old notification system and no iCloud.
Other than that, I would go with iOS 6.1.6. I have no idea why 6.1.3 is mentioned so much in this thread.