O Konsole, gnome-terminal (e todos os terminais GTK + 3 baseados em vte desde a vte 0.35.1), qterminal e st (da suckless) suportam cores verdadeiras no Linux, e o iTerm2 suporta-o no Mac.
Infelizmente, não há suporte a termcap / terminfo para esse recurso no momento e, portanto, também não há um valor correto para $ TERM. Nem as bibliotecas de tela ncurses e gírias suportam o recurso, e parece que elas exigem uma mudança incompatível com o ABI para conseguir isso.
O melhor que você pode fazer agora é definir TERM = xterm-256color (ou similar) e ter as seqüências de escape codificadas nos aplicativos (supondo que o aplicativo faça seu próprio tratamento terminal, ao invés de depender de ncurses).
Eu receio que levará anos para que esse recurso seja suportado corretamente em todos os níveis da pilha.