Cost determines how much experience you need to level up. An 80 cost puppet (fairies and stage 1 bosses and whatnot) will level up more than twice as fast as a 120 cost puppet (some final bosses or anyone implied to be exceptionally strong). For the purposes of just clearing the story, level matters way more than base stats, so the 120 cost ones are just kind of worse, in that sense.
Cirno is 80, and Mai is 90, so they make the game significantly easier than if you had picked, say, Suika.