My Atmega328 seems to be overkill, what should I use instead?
Using Atmel chips in the Arduino IDE

For the ATtiny45 and ATtiny85 you can use this library that you put in the same directory as your sketches (make a "hardware" directory, then unzip this in there).

I found lots of things just work, but not everything.  These chips are pretty tiny.  You only get 4 input/outputs (or 5 if you have a high voltage programming device), and you have to be careful which ones can produce the type of output needed by tone (probably only 2 of the pins).  These guys are in the $1.25 to $2.25 range.

You can also use ATtiny2313's, but I've not tried using the Arduino IDE with them.  I switched to using AVR style GCC, as its not much harder and if something breaks I know its my fault.  The 2313 has a ton more pins (not as many as the ATmega), hardware serial support, etc.  It is in the $1.50 to $2.50 range.

The ATmega328p is more in the $3.00 to $4.50 range (and currently is often out of stock).

You can think of the Arduino IDE as consisting of 3 main parts:


a nice, reduced programming language for AVR style chips (mostly by providing you with simple to use functions like tone)
a nice, easy to use upload mechanism for ATmega and larger ATtiny chips (the bootloader)
a nice GUI interface that makes it easy to use the right part when you need it


When you work with the ATtinyX5 chips, the bootloader doesn't work, but you can use an Arduino to program the ATtiny's very easily.  The library I linked to makes the first and third parts of the IDE available to you.

If you want something cheaper, but mostly the same as the ATmega328p, I would go with the ATtiny2313.  If you want something smaller, then the 8-pin ATtiny85 is nice, but it is not too much cheaper and lacks a lot of the nice features of the ATtiny2313 and the ATmega328p.

I haven't tried the other Atmel AVR product lines, but they definitely have others.  Luminet (mentioned in another answer) uses the ATtinyX4 line and has a modified IDE to work with them.  They appear to be in the $1.80 to $3.00 range.