You can't connect a host to a host
Actually you can, this has been part of the USB 3.0 spec when it was released in 2010. This requires a special cable if using USB-A to USB-A but if one or both hosts have USB-C then a common cable like that used to connect a hard drive or smartphone will work. Depending on the smartphone it may in fact be using host-to-host communications without the user knowing.
Connecting Windows or Linux hosts to each other by USB is supported on most any system with USB-C but it's not easy to setup, and even then unless or until someone writes some more software for this communication the utility is quite limited. Apple hardware supports USB 3.x host-to-host communication as well but most people will find it much easier to use Thunderbolt instead, it's faster, the operating system supports this function, and in the case of USB-C it uses the same port as USB 3.x. Thunderbolt has stricter cable requirements for host-to-host communications, some USB 3.x cables work for Thunderbolt, some don't.
I do wish that someone would bring USB host-to-host communications to the novice users, so many people ask for it. This is a software problem, all the hardware is there with perhaps some exceptions on early implementation of USB-C.
This distinction has historically been enforced by the connectors: hosts have type-A sockets, and peripherals have type-A plugs or type-B
sockets.
USB-C, however, uses the same connector for both hosts and
peripherals.
The "A type" and "B type" ports are not lost with USB-C, it's just not enforced with a physical connector any more. Enforcement is done electronically.
This makes me wonder what determines which one will be the host. Does
a USB-C cable have a "host end" and "peripheral end" that can be
distinguished electrically even though they look the same? Do the
devices negotiate which will be the host? If so, what criteria do they
use?
A USB cable with USB-C connectors on both ends will not have a host (or A type) and peripheral (B type) ends. The way the connectors work though someone could construct such a cable, but that would violate the USB specifications on how such cables are to be wired. I've seen non-compliant USB-C cables before and when constructed with care and a purpose they can be quite useful, the problem is that the cable would have to be marked in a way to point out it's unique purpose to avoid confusion and complaints. Making this distinction clear to users could be trivial to near impossible, which is why the people behind USB don't allow such cables to bear their trademarks or claim certification.
When connecting two hosts by USB-C a number of things can happen depending on the capability of the computers. If both computers support dual-role ports then the role each takes is random, and this can result in things like a phone charging a laptop even though that is not what the user wanted. The hosts will have a short memory on which role they had so reversing the role can be done by unplugging and reconnecting. Some people will flip the cable around in the mistaken belief that the cable has some built-in directionality, which is then reinforced by the role reversal. This can be proven false by disconnecting and reconnecting without flipping the cable.
Not all USB hosts have dual-role ports and so if one is host only and the other dual-role then the dual-role host will take on the peripheral role. As you discovered there is nothing interesting happening if two peripheral devices are connected by a USB-C cable.
Connecting two host only computers by USB-C will allow host-to-host communications but only if the correct settings have been made in the operating system. Depending on how the ports are configured there may be a kind of "master" and "slave" role playing but this is on software layer outside of USB-C and USB 3.x. They may take on peer/peer roles on this layer as well.
This is ignoring alternate modes on USB-C such as Thunderbolt, DisplayPort, and more. The way Thunderbolt works there is a peer/peer relationship, and the role of power source or sink is negotiated if needed. Video modes on USB-C, such as DP, HDMI, and MHL, have much simpler role negotiation as data for video, sound, device control, and a few more bits only go one way. When there is a bit of data going the other way, like an audio or Ethernet channel, then it is kept on a set of wires distinct for this purpose.
So it seems that there's a mandatory charging direction when a USB-A
port is involved, but with a native USB-C connection the devices can
somehow figure out the "right" direction for power to flow. How do
they determine that? What would happen if I connected two identical
phones together, or two laptops with USB-C ports?
There is a protocol for handling power, and it is called USB-PD. USB-PD is a bidirectional protocol that is independent from the flow of audio, video and other data, a protocol based in large part from older standards of USB-BCS (battery charging system). This is base on the lowest levels of USB power going back to USB 1.0 and 1.1. From that grew USB-BCS, and later USB-PD which are the standards on which others grew. Apple extended some of this to create their AppleID protocol, which works well when USB-BCS fails and USB-PDS is slow, expensive, and taxing.
Since there are a bunch of little questions above, here's the big
over-arching one: some elements of a USB connection must be
directional (host vs. peripheral, and charging direction), so how does
a USB-C connection determine which one is which?
USB-C is a port that can carry multiple independent data paths and each can negotiate which is going where. Power negotiation is relatively simple, a determination of the voltage and direction. This direction of power flow can be dictated by the capability of the host, and can change at any time based on need. The power host and slave have nothing to do with the direction of the data flow. That flow is negotiated independently on each of the four super speed lanes. The protocol can be unique as well. A USB lane will have a matching USB lane. MHL may have a matching lane, three such lanes, or no matching lane and go it allow.
USB4 allows for USB, Thunderbolt, and DisplayPort to share lanes. Each of these Super speed lanes can flow in any direction. That is independent from USB 2.0. Also independent is power flow.
USB, Thunderbolt, and DP can share data lanes but not when MHL or HDMI are around. HDMI demands all super speed lanes. MHL needs it's own lanes, and any not used can be occupied by only USB.