Case in point: I looked into Agda and ended up in a deep rabbit hole that involved something I had never heard of called "Walther recursion." Whether this qualifies as "nearly impossible" or merely "hard" is quibbling over terminology, not substance.
Note that you can still build useful programs this way since such languages can still allow certain forms of recursion such as primitive recursion, structural recursion etc... You can also use sized types [1] to allow even a larger set of (halting) programs.
[1] This is a way of compiler statically analyzing the size of each type (i.e. how many recursive constructors necessary) which puts an upper bound on the number of recursions need to be performed.
Now if you want to gain the ability to make serious proofs about your programs, one can make the argument you need non-TC.