I was hoping to find some suggestions for tiny servos to use with a miniature mechatronics project that I want to attempt (will be controlled by a TinyDuino).

Is anyone aware of ultra-tiny servos, or perhaps might have other ideas for miniature robotics? They don't need to be all that powerful.

You can try some of these:
http://www.hobbyking.com/hobbyking/store/__29547__HobbyKing_HK15318B_Low_Voltage_Micro_Servo_2_2g_11kg_08sec.html

I picked up some servos from them but haven't had the time to try them out.

The Cirrus CS-3 Micro Joule Servo is pretty small... slender and long, which could be great to stack back to back under a TinyDuino Stack. It is 20.1L x 6.1W x 6.1H mm but $50/ea according to servodatabase.com

For simple steering or actuation, Plantraco has some wonderfully small components. The starter set has a very small receiver and 2 MiniAct magnetic actuators, among other things. Microflight sells a The Deluxe Starter Set for $99. Microflight separately sells the MicroAct Magnetic Actuator for $7/ea and the MiniAct Magnetic Actuator for $7/ea. Here is a cool video about the MiniAct Actuator. They also have a nice tiny motor and gearbox selection. For a really tiny actuator, there is the NanoAct-Actuator.

The Ping Zheng 1.3G Servo without PCB PZ-15319A is 12.6L x 6.2W x 10.3H mm.

Nanomotion's EDGE miniature Piezo Motors are small. Providing unlimited linear or rotary motion, the EDGE motor uses compact ASIC-based driver, and can be operated with any servo controller. It is 13.5L x 7.6W x 3.15H mm.