Starting with 2d6+Cha at Medium makes sense. If we want the "+s" to scale, though, I guess we should go with +Str. No bother with me either way. And agreed to the frost giant!
Updated.
For the frost giant sample, let's stick with your suggested class skllls above (Hide, Listen, Move Silently, Spot, and Tumble). Climb and Jump should go.
Little is known about the creation of these fell creatures, through most sages agree that animate dead, a specialized delayed shatter (see below), and protective magics are involved. It is argued that create water and control temperature 10’ radius are also needed for the creation, suggesting that not only are there dark arts at play, but unholy prayers as well.
New Spell – Delayed Shatter
This spell is similar to the second-level Wizard shatter spell in the Player’s Handbook. The differences for delayed shatter are as follows: it is a third-level spell and has a casting time of 3, the spell can be cast only on a single object, and the duration lasts until the object on which the spell is cast is destroyed. All other statistics are the same as shatter. Since this spell cannot be cast on magical items, it is assumed that this is the first spell cast to create a crystal skeleton.
I'm not convinced we need to convert delayed shatter, but I could see requiring regular shatter and some low-level cold spell in conjunction with animate dead.

(Dungeons & Dragons)
Rulebook featuring "high magic" options, including a host of new spells.