If you could easily identify that a site you were on had cookies stored, and that one was about you being logged in, and it was plain simple to wipe that cookie then I'm sure you'd be happier about that situation. Couple that with a default to have them disabled - until you explicitly lend your browser a little more trust - to prevent ticking those boxes in a public place. And we might all feel a little better about them.
I guess cookies though are a solution to the leave me logged in checkbox. Another technology could be used. I personally hate them as they currently are.
Even key chain programs are difficult to understand. Safari uses user key-chain, Firefox uses it's own profile to store passwords. No consistency and headaches for users.