Agree that self-signed SSL certificates are treated as if they were the red-headed step-children of SSL. Perhaps if movements like Let's Encrypt[1] take off, self-signed certs will be a thing of the past.
StartSSL will use whatever certificate digest algorithm you used in your certificate signing request. Most openssl.cnf files distributed with Linux OSes set the default algorithm to SHA-1 - that's nothing to do with Startcom.
Simply specify an explicit algorithm if you want to get a certificate using that. For example, if you do:
and give them that CSR, you will get back a SHA-256 certificate.
EDIT: They also have a SHA-256 root (in most browsers, though you don't need a second-preimage-resistant digest algorithm for a /root certificate/) and SHA-256 intermediates at https://startssl.com/certs/ - go to the relevant class directory and there is a sha2 directory inside that.
StartSSL's interface is a huge pain. Let's Encrypt is hoping to offer things like modules for Apache and Nginx that make them take care of acquiring certs automatically, though we'll see.
[1]: https://letsencrypt.org/