First, salesforce.com actually does try to deliver messages encrypted using TLS, if your email server supports it. Use that configuration if you're concerned about casual Internet snooping.
If that doesn't satisfy your demands, consider these alternatives:
Use SSO. Their password is tied to their network login, so salesforce.com can't (and doesn't), supply a password. It's effective, and reduces maintenance.
Create the user first without generating an email, then reset their password. They'll get a notification of the password without a user name (at least, that's how it used to be; I'd have to check).
Set their password to a known value with setPassword
, and send them a message yourself telling them what the password was. No email need be generated at all using this method.
Enable two-factor authentication. You can set them up with a RSA-style mobile authentication. This means that, even if their account is compromised, you'd know virtually immediately, and could take steps to mitigate the issue. If you're really paranoid, freeze their account and require them to contact your IT group to unfreeze them for their first login. Or, simply set their profile to Read Only until they verify they are the correct user.
Conclusion: salesforce.com offers many different authentication schemes, and it's worth investigating all your possible options. The default message may seem "weak" (but honestly, it's not, unless your users' emails are already compromised), but the fact that they have to change immediately to a strong password-- as strong as you like-- suggests that there is little to worry about. IMO, if you're honestly concerned about security, you'd use SSO so that you maintained control over user passwords and could locally monitor their access.