I store my session token in a cookie, which is even worse because it's sent with every request.

It's not. The cookie only gets sent to the domains/servers you specify and is not accidentally exposed via browser history or copying a link.

Not in a URL generally, and if it is the only people who can see the full URL are the receiver and the sender if HTTPS is properly enabled.