Well, your questions is quite vague and perhaps overly broad. I'll answer your main question "what is the smallest," assuming you meant dimensionally, while keeping in mind that you also want the most powerful one in that size. The pricing of different chips like this will be fairly similar so I'll ignore that.
Next, I'm not sure what you meant by saying "capable of running Arduino" which may mean capable of having the Arduino bootloader installed or could mean being capable of running code written with Arduino libraries. I'll assume the latter since it's the most practical requirement. I'll also assume you want an Atmel chip since it will be the most directly compatible with the Arduino libraries.
So what is the most powerful of the smallest Atmel microcontrollers capable of running Arduino code?
The answer is probably the Attiny 10 which comes in a 2 x 2mm 8-UFDFN Exposed Pad package, or a 2.9 x 1.6mm SOT-23-6 package for about one dollar in small quantities.
Also see this Hackaday article on how to use the Attiny10 with Arduino.
Edit: After more research, I was unable to find an Arduino core for the Tiny10. So while you can program it with an Arduino using assembly or something, writing Arduino code for it won't work. The smallest Attiny with an Arduino core I could easily find is the Attiny13 in a 3 x 3mm 10-VFDFN package. The upside is that while not being that much bigger or more expensive, it's a way more capable chip for your project.