Does Google Cloud provide public hostnames for their Compute instances?

No, GCE doesn't offer hostnames for an instance. It does assign external IP addresses for each instance. Associating a DNS record with your instance is the only method to generate a hostname.

GCE does have built in private hostnames, inside the same network. For example two instances in the same VPC can ping each other by name

Instance 'test-instance': start server on :8080
Instance 'second-instance': curl test-instance:8080
// Response 'Hello World'

No. Source: FridayPush's answer (thanks! from his profile, seems worthy of trust for Google-Cloud things :-)).

The reason I wrote a separate answer is to make it clear that you can't have a public hostname totally through Google Cloud. You can either have an internal hostname totally through Google Cloud, or you'll need to do something outside of Google Cloud (e.g., own a domain name) to have a public hostname.