Kind of want to give my own take on existing suggestions. Spider-style climbing would be neat. For the next X seconds, ladders appear on vertical surfaces near the user's feet and disappear when the user moves away. Don't know how tough it would be to make them invisible, but it may not be essential. A lip in the wall would stop this cold too, but you can move more than up-and-down, which may be suitable for different classes than a grappling hook-type skill.
Skills that reduce or nullify food strain from different sources. One for jumping, one for dashing and so on (there's a so on, right?). Simple, probably useful.
Can block-placing skills take cues from the environment? I have an idea for a wall-summoning skill (could be temporary) that recognizes the kind of block exists at the location where the wall would spawn and creates a 5ish-high tower of that block directly on top of it. I hope I explained that well enough. The ice bridge sounds awesome!
Skill that causes all animals in an area to try and breed. Probably would be the butt of many jokes, but it's sounding useful from here. Reagent could obviously be wheat or another organic item, say a flower.