hey - that's what I've been struggling with for the past few days.
I've tried lots of header versions, but I haven't been able to get anything working correctly for display on all clients (yes, I've limited that ambition to a few of the most common clients and platforms -- Outlook, Eudora, Netscape, & some webmail / mac & pc).
Now I'm using a script by Richard Heyes --
http://www.phpguru.org/mime.mail.html
He has a setup ('example.2.php') that produces MIME encoded e-mail with embedded images for the HTML portion, and a plain text version for clients that can't or won't accept HTML mail (of course that's only good for clients that do MIME, but sending out HTML mail is starting to look like a percentage game, and having an embedded plain text version should help raise that percentage a bit).
It's working better than anything I've put together so far, but there are still a few problems:
1) Nothing shows up in my excite webmail account -- no HTML, no images, no plain text - nada
2) In my Eudora, the plain text version shows up on top of the HTML version, and God help me I cannot find a setting or preference that applies to this display
3) Another problem is that not all e-mail clients render HTML very well at all, even when it is displayed. I've kept my HTML as simple and plain as possible, but you can't count on a table row to hold a bgcolor, etc. It's taught me to think black on white works best!
I don't think you can sniff out client compatability ahead of time -- the mail server will send along whatever headers you give it, as long as they're formatted properly, as far as I can make out. If you want an e-mail to display plain text when the HTML doesn't get through, MIME is the stuff.
Anyhow, I think the guru's script is worth a look if you're trying to get the HTML out to as many people as possible.