as I understand it, an IV is used to create randomness to an encrypted message so that the message is difficult to crack from an attacker.
Actually, it's more so that if we encrypt several messages with the same key, their relationship is not obvious.
For example, consider CBC mode, and we encrypt two different messages, but those two messages just happen to start with the same 128 bits at the beginning. If we use the same implicit IV, they corresponding ciphertexts will also have the same 128 bits; hence the attacker will know that the two messages are related. That's more information than what we want to disclose to the attacker.
For example, say I add 16 random bits to the start of my message and encrypt only using a random key and an IV of 0s, would the output not have the same effect as using a random IV without my random bits?
Still assuming CBC mode: if you encrypt multiple messages with the same random key, well, 16 random bits aren't enough (because the probability that two different messages happen to be encrypted with the same random bits is just too high). That can easily be fixed by using more random bits.
If you use 128 random bits, well, it turns out that is precisely the same as doing normal CBC mode with a random IV (!); if the decryptor expects the IV immediately in front of the ciphertext (which is common), it doesn't even have to know you aren't doing the standard CBC mode implementation. In addition, the 'random bits' doesn't have to be random, unique is sufficient, and is a trick that is in use (it can save time; doing one additional block encryption can be cheaper than asking the RNG for 128 random bits).
On the other hand, if you're doing (say) counter mode instead of CBC, this is a really bad idea; you really do need to use a distinct IV for each message.
On the third hand, if you're going to encrypt only a single message with that key (which does happen), then you don't need to worry about the IV; you can use a default one, and you're fine.
