An easy (though sort of annoying) fix would be for the browser to only store cookies per-tab - so if I log in to site A in tab A, then open site B in tab B, the cookies set in tab A don't apply to tab B, which also means that if I open site A in tab B, I'll be asked to log in again; and also to delete any stored cookies when navigating away from the domain for which they were set, or when closing a tab, etc. This of course also applies to all other forms of local storage. A sort of a stronger version of the "delete all history when I close the browser" setting.
Now, I realise these will get very annoying very fast, so I suggest you could whitelist which domains can store things permanently and then only send them if the url in the location bar is from the domain which set them (because fuck iframes)... Of course iframes will need to work, so you'll also want to have whitelisting of cookies which can be used in an iframe from this or that domain.
All of which in the end has a pretty harsh setup for average users, but I'd like it.