Everybody uses RSA. If you stick to RSA, you certificate should be acceptable everywhere. Use a 2048-bit key size. ECDSA is nifty and very hipster, but won't work everywhere yet.
A RSA key is a RSA key. However, a certificate is also a signed object, and a signature algorithm begins with some hashing. Thus, a certificate will contain references to a hash function. Some modern browsers have apparently decided to scream and wail and shout when they see "SHA-1" in a certificate; therefore, to avoid dropping out of fashion, you need to use SHA-256. This should work on XP since SP3 (but not before). Take care that this is about the signature on the certificate, so really it is the problem of the Certification Authority that signs your certificate.
Whether you sign your certificate request with SHA-1 or SHA-256 as supporting hash function, should not matter. The CA extracts the public key from your request, pushes it in the new certificate, and then will use SHA-1 or SHA-256 depending on its configuration, regardless of what you used yourself to sign the request. At least that is how CA are supposed to work; some CA do weird things at times.