As stated in the title, I'm looking for an encryption algorithm with the characteristics that, when inputs are slightly different, the encrypted output will be VERY much different, to the point that no one will suspect that unencrypted inputs are quite similar when they compare the encrypted outputs.
The TDES encryption algorithm doesn't seem to reproduce the above characteristics. So is there such an algorithm?
What you want, if at all possible, is an IND-CPA (or, preferably, even IND-CCA2) secure encryption scheme. Such encryption schemes are by definition probabilistic (and/or stateful), so that even encrypting the exact same plaintext twice will produce completely different results.
Conveniently, there are plenty of block cipher modes of operation that provide IND-CPA security, as well as authenticated modes that even provide IND-CCA2 security (which includes resistance to active forgery attacks where an attacker may modify encrypted messages and observe the results of attempting to decrypt them). Triple DES can be used with most of these modes — but you really shouldn't be using it nowadays, since AES is both faster and more secure.
If you absolutely need your encryption scheme to be deterministic, so that the same plaintext always encrypts to the same plaintext, the next best thing you can have is DAE security. It's basically the same as IND-CCA2, except that because it's deterministic, an attacker can obviously tell if two encrypted messages have the same plaintext or not.
The first and most popular DAE-secure encryption method is SIV mode, although there are also newer and potentially faster schemes like GCM-SIV. All of these are designed (and standardized) for use with AES; while you could in principle used them with TDES, that would be less secure (particularly due to the smaller block size) and generally pointless.
Conveniently, SIV and other DAE-secure encryption modes have the useful feature that, if you include a unique nonce as associated data with every encrypted message, they become fully IND-CCA2 secure, and still remain DAE-secure even if you accidentally use the same nonce twice. This "nonce misuse resistance" is a very handy safety net to have, and IMO is a good reason to use AES-SIV (or AES-GCM-SIV) whenever possible.
Finally, I'd like to note that your description of your attempts so far doesn't really fill me with confidence that you know what you're doing. (That goes particularly for the fact that you mentioned using TDES, but not which mode you're using it in — that's kind of the crypto equivalent of saying that you're driving a 4-cylinder internal combustion engine from 1995, but not specifying whether it's in a car or a motorbike or a lawn mover.)
If all this talk of "nonces" and "modes of operation" and "IND-CPA/CCA2 security" goes straight over your head, I'd suggest either picking up a good introductory crypto book and/or just browsing this site until it no longer does.
While there are nowadays some relatively "foolproof" encryption APIs like NaCl crypto_secretbox available, you do still need at least enough basic crypto knowledge to understand the terminology and to be able tell a secure and well designed system from complete snake oil. Or you can just hire someone who does understand all this stuff to design your cryptosystem (and someone else to review it — which you really should do anyway).
Avalanche criteria
You are understanding the avalanche effect/criteria wrongly. The proper definition is given by Webster, A. F "On the design of S-boxes". Advances in Cryptology - Crypto '85 as
For a given transformation to exhibit the avalanche effect, an average of one half of the output bits should change whenever a single input bit is complemented.
Or, we can see that each of the bits has 50% chance to be complemented if you change only one bit.
The best is testing with some examples from the reverse. (this site is used)
the key is 0e1f35bbaf37a86b13cb84e06daeb538
the ciphertext (hex) the plaintext (hex)
0000000000000000 9d 9a f3 e0 42 34 ab f5
1000000000000000 2e 74 29 e0 6b c4 29 8c
0100000000000000 c5 5e 1b ee 38 6c 09 0c
0010000000000000 0a 9c c5 21 9a a1 b4 fb
0001000000000000 c3 ad 4b 6d 82 3e 30 20
The list can go on. The ciphertexts are very close, but as you can see the plaintexts are not. Similarly, you can check with 1-bit plaintext change.
Your claim is very big about 3DES. Even if we used DES, which is only broken due to the short key size and short block size, differential and linear attacks were not the real threat. However, what you are saying is that you can distinguish the ciphertext.
Ideally, Block ciphers are selecting permutations of 2^n elements by keys. Compared to the number of permutations the key size is very small. What we expect that the selection is random. If you believe that you can distinguish that DES is not selecting the permutations, go for it and publish.
Reusing IV
As Stephen Touset mentioned in the comments, reusing IV is very dangerous. You can see from Cryptography.
Suggestions
It is better to use Authenticated encryption modes as AES-GCM and chacha20-poly1305 which are in TLS 1.3.
However, you want to use same IV for encryption of different plaintext. You may look at AES-GCM-SIV where the IV is nonce.
AES-GCM-SIV is a fully nonce-misuse resistant authenticated-encryption scheme. Such schemes have the property that both privacy and integrity are preserved, even if nonces are repeated. To be more exact, encryption is a function of a nonce, the plaintext message, and possibly additional authenticated data (typically denoted AAD). In a fully nonce-misuse resistant scheme, if a nonce is misused (i.e., used more than once) then nothing is revealed unless the same message is encrypted multiple times with the same nonce.
