Making clever paint/tic-tac-toe/sudoku programs in Java/C++ are good exercises...but I lost interest in programming when I couldn't see it being used for more day-to-day practical tasks.
One specific topic I wish had been taught was regular expressions. In my first year of comsci classes, regexes were in the optional chapters of the book. Knowing about them would've led me to do more data-processing/information-gathering type programming, which is the track I am on now.
Plus, they're just damn plain useful in every coding context, even for project code-search-and-replace.