Incrementing nonces vs regular nonces?

I'll list the disadvantages of both

For random nonces:

• Random nonces obviously require a well seeded random number generator;
• There is more chance of a collision due to the birthday bound;
• Sequential nonces therefore usually require all bytes of the nonce (a counter could initially be encoded by a single byte);
• Random nonces need to be send separately from any other part of the message - keeping track of # of messages or using a message identifier doesn't work.

For sequential nonces:

• Sequential nonces are stateful, i.e. you need to keep state or you're prone to repeat them;
• There is a chance of collision if key values collide (this is a bit unfair, we generally don't have colliding keys, but maybe there is another weakness that can trigger identical key values);
• Sequential nonces may give away details of the protocol, as they are easily detected if sent with the message;
• It is required to specify endianness for random nonces (in e.g. WinZip a little endian counter was used for CTR mode, this is not common);
• You cannot use a random nonce and then e.g. switch to CBC mode which requires an unpredictable IV instead of just a nonce (without additional calculations; it is e.g. possible to encrypt the IV and use that value).
• If the nonce is chosen too small then the attacker knows exactly when they will start to "overrun" and repeat.