Even a self-signed certificate (like the one created in InfoPath) can be installed and used on client machines. The user simply needs to install it when opening the form, and I have done this a few times in the past when signed certificates just wasn't an option. However, user's may be scared by what they have to agree to when they install a self-signed certificate, so you will have to tell them it is OK while not being complacent about such security concerns. In an enterprise you probably don't want to do this and opt for a signed certificate from a valid authority. This could either be a certificate from an organization such as Thawt or Verisign, or it could be generated by the enterprise itself via a product such as Microsoft Certificate Server.
I had the same problem you had regarding a C# project and slow form load times. I have developed numerous forms before, mostly C# and I have never run into this. However, we have a complex, global network with numerous domains, and a somewhat convoluted path for access and authentication. The form is installed in a SharePoint server in one domain, the certificate technically comes from a different domain (albeit a parent domain) and access is currently provided via Citrix in yet another domain. We figured after a few hours of troublshooting that the problem was some sort of authentication issue and I suspected it had something to do with the certificate verification, but wasn't sure exactly where to look. Thanks to this post I now know, but I fear that it may not be acceptable for have users disable the option mentioned. Having said that, I am pretty sure it would be more difficult to address the network issues...Ah, the joys of enterprise computing!
UPDATE: I just noticed the date on the previous post...I don't expect to get a response :-)