I would look for a group music & movement type program for this age. My recommendations would be:
Harmony Road Music Course ( www.harmonyroadmusic.com
Yamaha ( http://usa.yamaha.com/music_education/
Music For Young Children ( www.myc.com
These programs start at 2 years or so, with singing, playing w/rhythm instruments, finger games, moving (hopping, stomping, marching), quiet songs, etc... The great thing about the programs above is that they also incorporate piano/keyboard activities, so kids are learning about black/white keys, highs/lows, 2 and 3 black key sets, and eventually, the actual notes on the piano (minus piano fingering at this age).
I use the HR program and teach several classes of 3 and 4 year olds. The 4 year old course is called 'Music in Me' and is a piano readiness course that includes the same activities as above, and also a book, workbook, cd. When they complete that course, they move into group piano class at about age 4 1/2-5. I currently have about 18 kids that started last September in group piano classes, having gone through the music/movement courses from about 18m on. They are awesome students and a great age to teach.
Check and see if a location is close to you.