Term::Menus and Term::ANSIMenu both look interesting, though I know at least Term::Menus doesn't do 3-column output like you're requesting. Does this need to be in a dumb terminal, or can you use Tk? (r.i.p. Nick)
---
It's all fine and dandy until someone has to look at the code.
Thanks. I have looked at Term:Menus, and as you say it only does a single column. It also forces the hotkey to be separate. Pretty much has to be dumb terminal. I am matching look and feel of an extant app.