It depends on what you want to do with the costume. For wearable costumes, the Lilypad (http://arduino.cc/en/Main/ArduinoBoardLilyPad) might be the ticket since it was designed to be small, and sewn into fabric.
If you don't need that many pins, there are various small Arduino boards that can be soldered onto small boards. For example, when it was a kickstarter project, I bought 3 digisparks, that I'm hoping will come before January (http://www.kickstarter.com/projects/digistump/digispark-the-tiny-arduino-enabled-usb-dev-board). After they satisfy all of the kickstarter backers, I imagine they will sell them retail. There is also the Teensy boards (Teensy USB Development Board), including the Arm based Teensy 3.0 that was just shipped to kickstarter backers (I have this also).
If you need a lot of pins to control various things, there is the Mega and the new Due.
I would say, given you have a year, don't make the decision on the final form factor now. Buy a development board like the Uno/Mega/Due now, and iterate on what you want. When you know exactly what you want, and how many pins/memory/etc. it has, you can look for a board with a smaller footprint.
In terms of power, you should obviously test what you have well in advance and make sure you have more than enough power with a margin in your batteries. For my Uno, I prefer to use a battery like the EZOPower 5000maH battery with 2 5volt/1amp outputs. I let my Uno run for a 3-4 days straight running blink before the unit ran out of power: http://www.amazon.com/EZOPower-External-Portable-Rechargeable-Emergency/dp/B0043622O4/ref=sr_1_2?ie=UTF8&qid=1351701776&sr=8-2&keywords=ezo+power+charger
You want to make sure all connections are secure, since costumes can endure a lot of movement. I still tend to have at least one thing fall off everytime I go out with my steampunk camera setup, and I have only done some minor stuff with the Arduino.
If you are going outside, you need to think about weather sealing.