hey, climbing parents. i took my kids climbing for the first time last weekend. they enjoyed it, but were extremely put off by the uncomfortable shoes. i know, they're not designed to be comfortable. i actually hate them myself, but i'm a grown up and i can ignore the discomfort easier than my kids.
Size them large enough to wear socks. They add a bit of slop, but my Veloces in a comfy size with light socks only hold me back on 5.10 and up vs. my Miuras, and even then only on tiny holds. The socks help even out pressure and provide some cushion, so much that I prefer the same shoes w/ socks instead of without.
Painful shoes are for projects. Until your kids are working on that 5.11c, comfort comes at a low cost.
Edit: oh, and kids grow. When/if you buy them shoes, get them as big as possible without seriously hampering their climbing. The snuggness will come slowly, and they may appreciate it eventually.
Yep, that's good advice. The few times my kid has gone, we,(myself and the guy renting us the shoes), made sure they felt comfortable on his feet, and that he had wiggle room, w/ or w/out socks. I think it's important for beginners, especially at that age, to be comfortable, or they might be turned off to the whole thing.