I think doing sorting algorithms, math problems and string manipulation hardly counts as "fun" when it comes to programming.
Rather get them to do some ascii animations (walk, wave, punch methods), ascci men, ascci dogs and birds etc. What about simplistic clones of zork? (lots of if else logic, multidimensional arrays perhaps).
I have found that to get students (at least younger ones) interested in programming staying away from the more formal cs examples is the way to go. Doing these more challenging game like projects, although slightly harder will eventually incorporate the more formal sorting, searching, string manipulation excercises into them anyway without them being the actual focus. They will be so distracted in that they are making a small game, they wont even notice their learning the formal stuff.