Speaking of Turbo Vision, another option would be to turn to one of the Linux ports of it. Though one would have to write a Perl binding for it first. Python has Perl beat here by having a binding: PyTVision, but I suspect it's no longer working (last updated in 2004). Being an old and DOS-based project (it was first released by Borland in 1992), Turbo Vision probably has zero or near-zero support for Unicode/wide characters.

I'm seriously considering dialog(1) now.