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.