Some ideas that come to mind include:
beat detection- trigger lighting effects, build a set of turntables that beat match themselves, or make a robot that dances along with the music you play for it
amplitude detection- make a simple vu meter with LEDS
frequency analysis- you could make a project that reacts to different frequencies in different ways, recognizes certain melodies, turns audio into MIDI data, or translates incoming frequencies into square waves with the tone() library
digital effects boxes/digital signal processing- check out what I did with my vocal effects box (all processing done with Arduino), lots of possibilities here: pitch bending, distortion, sampling, delay, reverb, granular synthesis, mixing, and much more... I've provided code in this Instructable that lets you sample at up to 38.5kHz. Here is another instructable describing how to set up a simple audio out circuit with Arduino.
digital recorder- with the addition of an SD card of course (the Arduino has very limited memory by itself), this opens up the possibility of looping large samples and doing lots of other digital manipulations to pieces of stored audio The circuits and code provided here are compatible with SD card shields that communicate via SPI.
graphical representations of sound- Arduino oscilloscope/visualizer
Feel free to use any of the info in this Instructable to put together an amazing project for the DIY Audio Contest! We're giving away an HDTV, some DSLR cameras, and tons of other great stuff! The contest closes Nov 26.
(x1) Microphone Radioshack 33-3038
(x1) TL072 Digikey 296-14997-5-ND or TL082 Digikey 296-1780-5-ND (TL081/TL071 are fine too) I used a tl082 in my examples
(x2) 9V battery
(x2) 9V battery snap connector Radioshack 270-324
(x1) mono audio jack 1/4" Radioshack 274-340 or Radioshack 274-252 or 1/8" Radioshack 274-333 or Radioshack 274-251
(x1) LED Digikey C513A-WSN-CV0Y0151-ND
(x1) 10kOhm potentiometer linear Digikey 987-1301-ND
(x3) 100kOhm 1/4watt resistors Digikey CF14JT100KCT-ND
(x1) 10uF electrolytic capacitor Digikey P5134-ND
(x1) 47nF ceramic capacitor Digikey P4307-ND
(x1) Arduino Uno (Duemilanove is fine too) Sparkfun DEV-09950
22 gauge wire