I like the idea. I could imagine a client with an "Automatically mix coins" advanced option in a menu, along with a quick dialog box about the anonymity benefits, but constant transaction fees.
Transaction fees will be completely avoidable if the client strictly selects txids that can be spent without incurring any fees. In fact, the logic for selecting txids to mix should completely exclude unconfirmed transactions as well as transactions that aren't old enough to be spent without a fee.