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.
Simply specify an explicit algorithm if you want to get a certificate using that. For example, if you do:
$ openssl req -new -sha256 -newkey rsa:4096 -keyout foo.key -nodes
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.