For RSA to work, we require that its public key function $x\mapsto x^e\bmod(p\;q)$ be a reversible mapping on $[0,n)$. With $p$ and $q$ coprime, that's equivalent (by the CRT) to $x\mapsto x^e\bmod p$ being a reversible mapping on $[0,p)$ and $x\mapsto x^e\bmod q$ being a reversible mapping on $[0,q)$. With $p$ and $q$ prime, that's equivalent to $e$ being coprime with both $p-1$ and $q-1$.
We could choose for $e$ the smallest integer greater than 1 that is coprime with both $p-1$ and $q-1$ (implying $e$ odd and at least $3$ for large primes $p$ and $q$). That's not too long to find by trial and error. However, it is customary to use $e$ at least 16-bit so that $e\ge65537$. This is mandated by some standards (sometime: for encryption only), and justified if we use an ad-hoc padding (e.g. RSAES-PKCS1-v1_5) because it mitigates padding oracle attacks to some degree.
The most common practice is to choose $e=65537$, and then choose $p$ with $p\bmod e\ne1$, which ensures $e$ is coprime with both $p-1$, since $e$ is prime; same for $q$.
When using a secure padding, and no rule forbids it, we can choose $e=3$, and then choose primes of the form $3k+2$.