You can still use a curses based "GUI", where dialog boxes are built from text characters, and tab or arrow keys to move between selections. Minimal dependencies, but the chewy GUI goodness windows users depend on.
EDIT: You wouldn't want to damage their innocence with a bare naked command line, now, would you?