Lego Mindstorms NXT includes a visual workflow programming language called NXT-G, which is based on LabView. Simple NXT-G programs are easy for beginners to put together, but venture outside of a window's worth of building blocks and both the visual language and the program editor start to bog down. You can upgrade to LabView Educational Edition, but it's the same visual language. Anyone who has used a text-based programming language (basically any other programming language) starts to miss typing commands in a file editor pretty fast, and professional programmers are usually eager to teach their kids text-based languages.
Thanks to Lego's noble and common sensical offering of open development libraries and specs for the NXT, there are quite a few alternative programming languages and environments to choose from, both commercial and free. The most popular free solution appears to be NBC & NXC, an assembly language and a C-like threaded high-level language, respectively. The BricxCC IDE is only available for Windows, but the command-line assembler and compiler are available as source and as executables for Mac OS X and Linux. The book NXT Power Programming covers NXC, NBC, and BricxCC in 560 pages.
While I haven't tried it yet, I'm intrigued by pbLua, a Lua compiler that runs on the NXT brick itself. Loading programs is just a matter of transferring the source code files over USB or Bluetooth. This requires replacing the brick's firmware, but it's easy enough to fetch the original firmware from Lego to restore it. (In contrast, NXC programs don't require customized firmware.) For fans of IDEs, the site recommends using Eclipse with an appropriate Lua plugin, though this provides no special NXT programming or debugging features.
The Wikipedia article on Mindstorms has a survey of programming environments. Chris Anderson at Wired recommends RobotC, a C-like language and $30 Windows-only IDE developed at the Carnegie Mellon Robotics Academy with an interactive real-time debugger. (I'd gladly pay $30 if there were a Mac version.) Dick Swan, an author of RobotC, has a write-up of various options with excellent comparison charts, though I suspect it's slightly out of date.
Dick's charts highlight another good reason for choosing an alternate programming language: execution speed. RobotC claims an execution speed increase of as much as 130 times over NXT-G. Essential if you're going to attempt a Sudoku solver (which was written in NXC).
Oh by the way, when I linked that Sudoku solver video, I overlooked that the inventor has a great website with building instructions and NXC source code, and the same for a nice Rubik's cube solver.