I read somewhere that if used incorrectly, RSA has the security of the lowly Caesar cipher. To get around this, one is supposed to add a pad of (pseudo-)random numbers to the message. Do you put the pad at the beginning of the message, or at the end? Or both?

https://en.wikipedia.org/wiki/Optimal_asymmetric_encryption_padding

I am not aware of an attack that could exploit e being a small number. But what's wrong with making e be a random number between 0 and p*q? Technically you would have to verify that you didn't pick a multiple of p or q, but let's not worry about things that will not happen. :)

It has to be coprime to both p - 1 and q - 1, otherwise the security is considerably weakened and/or the encryption is not reversible. Practically speaking the reason we use 3, 17 or 65537 for e is because they have a low Hamming weight (due to being of the form 2^N + 1) which means that exponentiation by such e can be made very efficient (log2(e) exponentiations and 1 multiplication, which is optimal). This is virtually the only technical redeeming quality of RSA in the era of elliptic curve cryptography because properly-optimized RSA encryption with public exponent 3 is actually faster than ECC. Really, the only public exponent you should be using is 3, anything else comes from the misguided idea that small e are weak; they are not with proper padding, to the best of our knowledge, and to be honest, if there is a vulnerability with e = 3, there is probably also a vulnerability with any small e.

Also keep in mind that many RSA implementations will not necessarily function with arbitrary e; they may be configured to operate with only a restricted set of small standard exponents. Furthermore using a random e opens you up to a bunch of new attack vectors, in particular side channel attacks: you need to generate your e from something, probably the same source you generated your p and q from, so that gives you one more thing to screw up that an adversary can exploit. I would strongly discourage the use of a random e unless you like your encryption being unnecessarily slow and/or broken.

I think one of the main reasons people got the idea that using a small public exponent was a bad idea was the related-message attack that was popular a while back. Basically if you use plain RSA to send the same message to "e" different people with the same public exponent "e", then the message can be recovered by using each recipient's public key through a nice number-theoretic algorithm. But, of course, this only works because no padding scheme was used, and without secure padding there are far worse attacks that await you anyway.