In reply to ClimberEd:
Where you based? I think outdoors often Bette for themthan indoors at that age. They can sramble up mods, or even bits that aren't routes much better than they will a wall.
Definitely full body harness at that age - little ones are top heavy and have no hips to keep a sit harness on.
Our wall lets them in at any age, and is free for under 5s as they get bored quickly.
The teddy rescue that someone else mentioned is always a favourite. If the wall is quiet they may enjoy just swinging, so put them on a rope at the bottom of an overhang and lift them up and swing them (if the wall staff don't mind!).
Have fun, and as others said, don't be pushy!!