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!
Well I quite liked the idea of using d4s just for the sake of variety, but I'd be OK with 2d6 as the base for a Medium sized Crystal Skeleton with Strength as the bonus stat. That would make the progression:
Tiny or smaller 1d6
Small 1d8
Medium 2d6
Large 3d6
Huge 4d6
Gargantuan 6d6
Colossal 8d6
Which is pretty close to the d4 version.
Glad you liked the idea of using a Frost Giant as a sample creature. Most of its stats will fall out simply by applying the template to the SRD Frost Giant, we just need to select some skills and feats.
The Frost Giant's feats of Cleave, Great Cleave, Improved Overrun, Improved Sunder and Power Attack are a decent selection. We could leave it unchanged, or swap out Great Cleave for Weapon Focus (claws) and Improved Sunder for Lightning Reflexes.
As for skills, its lower Intelligence means it will have only 17 skill points. Of the SRD giant's skills, Craft seems rather unlikely and Intimidate won't be very effective with a Charisma of 1, so how about putting them in the remaining skills of Climb, Jump and Spot.
The SRD Frostie has Climb 4, Jump 4, Spot 10 for 18 SP, so we can just knock a rank off Spot and call it a day. That would make the sample monster:
Crystal Skeleton, Frost Giant
Large Undead (Cold)
Hit Dice: 14d12 (91 hp)
Initiative: +4
Speed: 40 ft. (8 squares)
Armor Class: 11 (-1 size, +2 natural), touch 9, flat-footed 11
Base Attack/Grapple +7/+20
Attack: Claw +15 melee (1d6+9)
Full Attack: 2 claws +15 melee (1d6+9)
Space/Reach: 10 ft./10 ft.
Special Attacks: Death throes
3d6+9
Special Qualities: Damage reduction 5/bludgeoning, darkvision 60 ft., immunity to cold, undead traits, vulnerability to fire
Saves: Fort +4, Ref +4, Will +9
Abilities: Str 29, Dex 11, Con —, Int 4, Wis 10, Cha 1
Skills: 17 [
Climb +13, Jump +17, Spot +9?]
Feats: Improved Initiative (B) plus 5
Environment: Any cold
Organization: Any
Challenge Rating: 7
Treasure: None
Alignment: Always neutral evil
Advancement: —
Level Adjustment: —