Agreed, although I see Lisp has gotten a second mention since your post. Lisp was my first thought when I read the question. (Well, the first serious one... "Perl 6" came to mind first, but it was a joke answer.) I took the Scheme class based on Structure and Interpretation of Computer Programs in college and I remember it as having been by far the most fun language I've ever dabbled in, although that may have been mostly the novelty of it being so different from anything I'd done before. Unfortunately, the course didn't go into the language deeply enough to actually do anything useful with it, so I never touched the language again after the course was done. (I should go back and play with it some more... I might even still have the book...)

As others have said, you can't go wrong with C, but I'm not sure whether it's as different as you might be looking for.