Servos are one of the easiest things to control with an Arduino. With a solenoid you will almost certainly need to add a transistor and some resistors to link it to the Arduino.
Some of the servos are very small - and cheap. I have some that measure 22x30x12 mm and you can get them much smaller than that. Have a look on the HobbyKing website.
...R