The tz database *itself* is no longer installed by glibc as of 2.16 (but is still in the source tree for the sake of testing).
The tz-manipulation code must stay, because widely-used functions in the exported API use it (notably tzset(), gmtime() and localtime()).
The locale support is very definitely not legacy: the C library is where all the internationalization code is located (found in libintl on many other Unix platforms). It is part of the API and ABI, used by every single internationalized program (which is most of them, these days) and can never ever be removed. (And printf() needs locale support for international printing of the decimal point and thousands grouping characters, and for the I alternative-output-digit flag character.)