GoDaddy has been around for at least a few years, but yes, VeriSign does sound more like a "trustable" company. The quality of their certificate may be just as good. But it's a matter of what the public trusts.

Since posting this question, I've discovered in doing more research and talking with mamallamadevil that the GoDaddy certificates are probably just as good, but VeriSign has the name recognition going for it. With the gov't. cracking down on security, if they do decide they want a certificate, it'll probably be VeriSign. But it was primarily my boss who was lobbying for a certificate in the first place, not the client.