For CTR, the requirement is that the counter value does not repeat (for a given key). The biggest gotcha with counter mode is that it is not enough for the IV (the initial counter value) not to repeat.
It doesn't matter whether the counter value is predictable. If you can arrange for the counter to start at 0 and to increase by 1 for each message block, that's a very good way of using CTR. Note that with multiple messages, this means that the first message uses the counter values $0, 1, 2, \ldots, a$, then the second message uses counter values $a+1, a+2, \ldots, b$, the third message uses $b+1, b+2, \ldots, c$, and so on.
Let me illustrate what goes wrong with a repeating counter value. Let $E$ be the block encryption function and write $\langle n\rangle$ for the encoding of a counter value $n$ as a block. If you send two two-block messages $P_0||P_1$ and $P'_0||P'_1$ (where each $P^{(j)}_i$ represents one block), one with the IV $n$ and the next one with the IV $n+1$, then the respective ciphertexts are $C_0||C_1 = (E(\langle n\rangle) \oplus P_0) || (E(\langle n+1\rangle) \oplus P_1)$ and $C'_0||C'_1 = (E(\langle n+1\rangle) \oplus P'_0) || (E(\langle n+2\rangle) \oplus P_1)$. Note how both these ciphertexts use $E(\langle n+1\rangle)$. An adversary can xor the two ciphertext blocks that use the same counter value, and their encryption mask cancels out: $C_1 \oplus C'_0 = P_1 \oplus P'_0$. This is often enough to guess some or all of the plaintext blocks. For example, many messages contain a known or mostly-known header, and in this example of repeating the counter value this turns into revealing the content of what's 16 bytes after the header in the first message.
If you can't keep track of which counter values have been used, a common technique to avoid repetition is to use a 16-byte random for the IV. This makes the chance of reusing a counter value small enough that it won't happen in practice.
In most cases, you should use a standard authenticated encryption (AEAD) mode instead, for example SIV or or GCM-SIV or GCM or CCM. This has two benefits. One is that the ciphertexts are authenticated: when decrypting, you can verify that the ciphertext was not changed. (It is impossible to verify a ciphertext's authenticity without the secret key. An adversary can still swap two genuine messages, so authenticity does not quite imply integrity.) The other advantage of using a standard AEAD mode is it's enough for security that the counter value does not repeat: there are no other subtle conditions. SIV modes have the advantage that even if the IV accidentally repeats, this can only reveal that the messages are identical, it won't reveal anything about their content.
Using AES-256 rather than AES-128 only improves security against quantum computers, in case they become practical.