For GUIDs, on the other hand, I'd probably just use a good standard cryptographic hash function like SHA3 rather than assuming that there will be no more than n "clients". But it depends on the purpose, of course.
One would assume that public keys are always easy to guess, because they are public? Hopefully they are not used for any sort of public authentication protocol...?
Some (few?) solutions allow for communication without TLS. In that scenario the API key is usually paired with a shared secret used for signing all messages, so the user is under no obligation to prevent the API key from becoming known to others.
Doing that securely and protecting against replay attacks is non-trivial though.
Version 1 had a serious flaw [0] related to how the string to be HMAC'd was constructed. It used an appropriate and well-studied cryptographic building block (HMAC-SHA1) and is an excellent case study in why using the right building blocks isn't sufficient to have a secure protocol.
Version 2 fixed the issues with version 1, but it in turn has been superseded by v4 [1] (no idea what happened to v3). A v4 signature uses a derived key for the HMAC, and included in the derivation is the current date as well as the AWS region you're making the call to. Beyond time-based replay attacks, this also prevents an attacker from capturing a valid request to eg US-EAST-1 and replaying that request in a different AWS region.
0: http://www.daemonology.net/blog/2008-12-18-AWS-signature-ver...
1: https://docs.aws.amazon.com/general/latest/gr/sigv4_changes....
Regardless, there are many possible cases where you wouldn't be able to use TLS for whatever reason, though it's very rare.
Edit: Parent is asking "What are we hashing?", but the article says "Every language has a decent crypto package for generating random hashes".