I advocate education over legislation, or at least heavy-handed legislation...

I agree with you here. As people learn more about security I'm sure the situation will improve somewhat. The insurance industry will play a major role in this education as well. As I noted earlier if companies see much higher premiums for using, oh lets say, a Microsoft product, they might consider looking at alternatives a little closer.

Existing laws on false advertising should be employed: a company advertising their product as "secure" bundled with a EULA saying "you're on your own and you can't sue us" strikes me as disingenuous.

This would solve a lot of the problems. Consider Oracle's "Unbreakable" campaign. If they knew for certain they'd face lawsuits over false advertising they might have taken a little more care in making their claims.