Also note that "join" wasn't made a string method to "make it easy to find"; it's a string method because we had to figure out some way make join work on multiple string types back when Unicode was added. At that time, we imagined that Python might grow even more string types (how about encoded strings to save space, or binary buffers?), and it wasn't obvious how to create a "join" primitive that would find the right implementation, without having to know about all available types. We finally decided that dispatching on the separator made more sense than, say, dispatching on the first list item.
Given this, the obvious solution was to make the "join(seq, sep)" function call "sep.__join__(seq)". Changing __join__ to join was a pretty small step; after all, there might be cases where it would make sense to write sep.join(seq) in application code, at least if you happened to have the separator in a variable with a suitable name.
The "sep.join(seq) is more pythonic" is a much later concept.
And for what it's worth, the "let's dispatch on the separator" approach didn't work in practice; in order to handle sequences with both 8-bit and unicode strings, both implementations now know about the other string type.
So instead of a single function that does the right thing (but has to be taught about each new string type), we now have two separate join methods that both knows about the other string type. If we add another string type, we'll end up with three implementations, each of which has to know about two different types. And so on.
But who cares about new string types these days; it's not like anyone's actually using strings now that we have iterators ;-)