Ignoring a learning curve for the sake of argument, the most effective UI's tend to be command-oriented. If you memorize the abbreviated commands, you don't have to traverse menu trees. Command-line interfaces can still have menus for newbies.

For example, pressing Enter or giving the command "m" or the fuller "menu" at the command prompt may give a menu similar to:

   1 - Search for employees (SE)
   2 - New hire (NH)
   3 - Department transfer (DT)
   4 - Etc.
   0 - Back to prior menu [app-wide convention]
   Command: __

Here newbies just enter menu numbers; but next to each menu is a shortcut command, such as "DT". After they get experienced, they start using the shortcut commands to jump across the menu tree as needed, they are usually global. It's like a Go-to (gasp!). The prior stuff is still on the screen for reference because they wouldn't get a menu when using the shortcut commands; it only shows up if you ask for one.

And the shortcuts may take optional parameters, such as "SE gar" to search for all employees with a last name starting with "Gar". (Without the parameter, they get a typical search form.)

Before GUI's, I worked with users directly to gradually fine-tune such gizmos, and after a while their productivity screamed. They loved me and even forgave my lack-luster people skills.